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 five vertices has the Erdős-Hajnal property

Statement

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

Facts & Assumptions

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

[L1]

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

[L2]

The bull, $C_{5}$ , $P_{5}$ , and $\overline{P_{5}}$ have the Erdős-Hajnal property (The bull graph has the Erdős-Hajnal property, The five-cycle has the Erdős-Hajnal property, The five-vertex path and its complement have the Erdős-Hajnal property).

[L3]

The prime five-vertex graphs are exactly the bull, $C_{5}$ , $P_{5}$ , and $\overline{P_{5}}$ (The prime five-vertex graphs are exactly the bull, $C_{5}$ , $P_{5}$ , and $\overline{P_{5}}$ ).

[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 $H ≅ H_{1} [v \to H_{2}]$ and $∣ V (H) ∣ = 5$ with $∣ V (H_{1}) ∣, ∣ V (H_{2}) ∣ \geq 2$ , then $∣ V (H_{1}) ∣ + ∣ V (H_{2}) ∣ - 1 = 5$ , so each factor has at most four vertices.

Proof

technique · cases

1.1L1

[assume-case small] If $∣ V (H) ∣ \leq 4$ , then [L1] gives the result.

1.2givencases

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

2.1step 1.2L2L3

[assume-case prime] If $H$ is prime, then [L3] shows that $H$ is isomorphic to one of the four graphs listed in [L2]. Therefore $H$ has the Erdős-Hajnal property.

2.2step 1.2L1L4L5F1

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

3.1step 1.1step 2.1step 2.2cases-exhaustive∎

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

Depends on

Used by

Dependency tree · two levels

45 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)
Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Section 1 (standard reference, not scraped)