How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 5 results · all verified · 4 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Star Expansions and the Erdős-Hajnal Property — Examples

1 · Prerequisites

2 · Summary

These examples keep the finite witnesses on the page side rather than inside the long A-page proofs. Each verification is an adjacency audit in a concrete star-expansion.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31Open item page →

The star-expansion of the four-vertex path

Example

Let $P_{4}$ have vertices $b_{1}, b_{2}, b_{3}, b_{4}$ in path order. Its star-expansion has additional vertices $a_{1}, a_{2}, a_{3}, a_{4}, v$ and edge set ${b_{1} b_{2}, b_{2} b_{3}, b_{3} b_{4}} \cup {a_{i} b_{i} : 1 \leq i \leq 4} \cup {v a_{i} : 1 \leq i \leq 4} .$

Facts & Assumptions

Given: The path $P_{4} = b_{1} - b_{2} - b_{3} - b_{4}$ .

[L1]

The star-expansion adds a tooth $a_{i}$ adjacent to its matched vertex $b_{i}$ and to the root $v$ , with no other edges incident with $a_{i}$ ; the root is adjacent only to the teeth (The star-expansion of a graph).

Verification

technique · direct finite check

1.1L1

Applying [L1] to the four path vertices gives the eight new edges $a_{i} b_{i}$ and $v a_{i}$ for $1 \leq i \leq 4$ , together with no others incident to the new vertices.

2.1step 1.1∎

Keeping the original path edges $b_{1} b_{2}, b_{2} b_{3}, b_{3} b_{4}$ and adding exactly the edges from step 1.1 yields the displayed graph.

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31Open item page →

The star-expansion of the four-vertex path contains an induced five-cycle

Example

In the star-expansion of $P_{4}$ , the vertices $v, a_{1}, b_{1}, b_{2}, a_{2}$ induce a five-cycle.

Facts & Assumptions

Given: The star-expansion of $P_{4}$ with root $v$ , teeth $a_{1}, a_{2}$ , and path vertices $b_{1}, b_{2}$ .

[L1]

The only edges using the new vertices are $v a_{i}$ and $a_{i} b_{i}$ (The star-expansion of a graph).

Verification

technique · direct finite check

1.1L1

Among the chosen five vertices, the edges are exactly $v a_{1}, a_{1} b_{1}, b_{1} b_{2}, b_{2} a_{2}, a_{2} v$ .

2.1step 1.1L1∎

No chord is present: $a_{1}$ and $a_{2}$ are nonadjacent, neither tooth is adjacent to the wrong path vertex, and the root is not adjacent to $b_{1}$ or $b_{2}$ . Hence the chosen vertices induce a five-cycle.

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31Open item page →

The star-expansion of the four-vertex path contains an induced six-cycle

Example

In the star-expansion of $P_{4}$ , the vertices $v, a_{1}, b_{1}, b_{2}, b_{3}, a_{3}$ induce a six-cycle.

Facts & Assumptions

Given: The star-expansion of $P_{4}$ with root $v$ , teeth $a_{1}, a_{3}$ , and path vertices $b_{1}, b_{2}, b_{3}$ .

[L1]

The only edges using the new vertices are $v a_{i}$ and $a_{i} b_{i}$ (The star-expansion of a graph).

Verification

technique · direct finite check

1.1L1

Among the chosen six vertices, the edges are exactly $v a_{1}, a_{1} b_{1}, b_{1} b_{2}, b_{2} b_{3}, b_{3} a_{3}, a_{3} v$ .

2.1step 1.1L1∎

The teeth create no further chord, and the path contributes no edge $b_{1} b_{3}$ . Hence those six vertices induce a six-cycle.

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31Open item page →

The star-expansion of the four-vertex path contains an induced seven-cycle

Example

In the star-expansion of $P_{4}$ , the vertices $v, a_{1}, b_{1}, b_{2}, b_{3}, b_{4}, a_{4}$ induce a seven-cycle.

Facts & Assumptions

Given: The star-expansion of $P_{4}$ with root $v$ , teeth $a_{1}, a_{4}$ , and path vertices $b_{1}, b_{2}, b_{3}, b_{4}$ .

[L1]

The only edges using the new vertices are $v a_{i}$ and $a_{i} b_{i}$ (The star-expansion of a graph).

Verification

technique · direct finite check

1.1L1

Among the chosen seven vertices, the edges are exactly $v a_{1}, a_{1} b_{1}, b_{1} b_{2}, b_{2} b_{3}, b_{3} b_{4}, b_{4} a_{4}, a_{4} v$ .

2.1step 1.1L1∎

The path contributes no nonconsecutive edge, and the two teeth touch only the root and their matched path vertices. Hence the chosen vertices induce a seven-cycle.

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passaudited 2026-08-31Open item page →

The star-expansion of $K_{3}$ contains the hatted five-cycle

Example

The star-expansion of $K_{3}$ contains an induced hatted five-cycle.

Facts & Assumptions

Given: The star-expansion of $K_{3}$ .

[L1]

The A-page lemma proves this containment directly (The star-expansion of $K_{3}$ contains the hatted five-cycle).

Verification

technique · direct

1.1L1

Apply [L1] to the star-expansion of $K_{3}$ .

2.1step 1.1∎

The chosen six-vertex induced subgraph is exactly a hatted five-cycle.

Star Expansions and the Erdős-Hajnal Property — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The star-expansion of the four-vertex path

Example

Facts & Assumptions

Verification

The star-expansion of the four-vertex path contains an induced five-cycle

Example

Facts & Assumptions

Verification

The star-expansion of the four-vertex path contains an induced six-cycle

Example

Facts & Assumptions

Verification

The star-expansion of the four-vertex path contains an induced seven-cycle

Example

Facts & Assumptions

Verification

The star-expansion of K3K3​ contains the hatted five-cycle

Example

Facts & Assumptions

Verification

Sources

The star-expansion of $K_{3}$ contains the hatted five-cycle