TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-01

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.

Every graph on at most four vertices has the Erdős-Hajnal property

Statement

Every finite graph $H$ with $∣ V (H) ∣ \leq 4$ has the Erdős-Hajnal property.

Facts & Assumptions

Given: A finite graph $H$ with $∣ V (H) ∣ \leq 4$ .

[L1]

Every graph on at most three vertices has the Erdős-Hajnal property (Every graph on at most three vertices has the Erdős–Hajnal property).

[L2]

The graph $P_{4}$ has the Erdős-Hajnal property (The four-vertex path has the Erdős-Hajnal property).

[L3]

Every prime graph on at least four vertices contains an induced $P_{4}$ (Every prime graph on at least four vertices contains an induced P_4).

[L4]

A finite graph with at least two vertices is prime exactly when it is not a nontrivial substitution (A graph with at least two vertices is prime exactly when it is not obtained by substituting one graph on at least two vertices for a vertex of another graph on at least two vertices).

[L5]

Substitution preserves the Erdős-Hajnal property (Alon–Pach–Solymosi: if $H_{1}$ and $H_{2}$ have the Erdős–Hajnal property, so does the graph obtained from $H_{1}$ by substituting $H_{2}$ for a vertex).

[F1]

If $∣ V (H) ∣ = 4$ and $H$ contains an induced $P_{4}$ , then that induced copy uses all four vertices, so $H ≅ P_{4}$ .

[F2]

If $H ≅ H_{1} [v \to H_{2}]$ and $∣ V (H) ∣ = 4$ with $∣ V (H_{1}) ∣, ∣ V (H_{2}) ∣ \geq 2$ , then $∣ V (H_{1}) ∣ + ∣ V (H_{2}) ∣ - 1 = 4$ , so each factor has at most three vertices.

Proof

technique · cases

1.1

[assume-case small] If $∣ V (H) ∣ \leq 3$ , then [L1] already gives the Erdős-Hajnal property for $H$ .

1.2

[assume-case four] Assume $∣ V (H) ∣ = 4$ . We distinguish whether $H$ is prime.

givencases

2.1

[assume-case prime] Suppose that $H$ is prime. Then [L3] gives an induced $P_{4}$ in $H$ , and [F1] forces $H ≅ P_{4}$ . Therefore $H$ has the Erdős-Hajnal property by [L2].

step 1.2L2L3F1

2.2

[assume-case nonprime] Suppose that $H$ is not prime. Since $∣ V (H) ∣ = 4 \geq 2$ , [L4] yields a substitution representation $H ≅ H_{1} [v \to H_{2}]$ with $∣ V (H_{1}) ∣, ∣ V (H_{2}) ∣ \geq 2$ . By [F2], both factors have at most three vertices, so [L1] gives the Erdős-Hajnal property for $H_{1}$ and $H_{2}$ . Applying [L5], the substitution $H$ also has the Erdős-Hajnal property.

step 1.2L1L4L5F2

3.1

The cases in steps 1.1, 2.1, and 2.2 exhaust all graphs with at most four vertices. Hence every such graph has the Erdős-Hajnal property.

step 1.1step 2.1step 2.2cases-exhaustive∎

Depends on

Used by

Every graph on at most five vertices has the Erdős-Hajnal property Theorem

Dependency tree · two levels

42 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Maria Chudnovsky, The Erdős-Hajnal Conjecture — A Survey, Section 2 (standard reference, not scraped)
Tung H. Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Section 1 (standard reference, not scraped)