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.
The theorem reaches an induced witness
Example
The five-vertex path is -free but is not -free. More generally every -free graph is -free, because the vertices of induce . Thus the -free theorem applies to a strictly larger forbidden-pattern class than the earlier -free theorem.
Facts & Assumptions
Given: The -graph on , the path on , and an arbitrary finite graph .
The -graph has vertex set and edge set (The -graph and co-).
The path has vertex set and edges for , and no others (Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
An induced embedding of in is an injection preserving adjacency and nonadjacency on distinct pairs; is -free when no such embedding exists (Induced embeddings and induced copies of a graph, -free and -free graphs under the induced-subgraph convention).
There is such that every nonempty -free graph has a clique or stable set of size at least (The -graph has the Erdős-Hajnal property).
The graph has the Erdős-Hajnal property, and an Erdős-Hajnal constant for the -free class is a positive exponent bounding the homogeneous number of every nonempty member from below by to that exponent (The five-vertex path and its complement have the Erdős-Hajnal property, The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number ).
Verification
The identity map on preserves adjacency and nonadjacency, so it is an induced embedding of in itself by [L3]; hence is not -free.
The six-element set has no injection into the five-element set ; hence no induced embedding of in exists, and is -free.
Suppose the finite graph is not -free. By [L3] there is an induced embedding of in . Its restriction to is again an injection preserving adjacency and nonadjacency, and by [L1] the induced subgraph of on those five vertices has exactly the edges , which is a under [L2]. So is an induced embedding of in , and is not -free. Contrapositively, every -free graph is -free.
By step 1.3 the class of -free graphs is contained in the class of -free graphs, and the containment is strict because the graph itself is -free by step 1.2 yet is not -free by step 1.1.
The theorem [L4] bounds every nonempty graph in the larger -free class, hence in particular every nonempty graph in the -free class, whereas the earlier theorem [L5] concerns only that smaller class. Since both theorems merely assert the existence of positive exponents, step 2.1 is a strict inclusion of hypothesis classes and implies no comparison between the two exponents.
The witness , the general inclusion of step 1.3 and the strictness of step 2.1 verify all assertions of the example.
Remarks
- This example is a leaf: it is homed on the companion examples page and no later item cites it.
Depends on
- The $E$-graph has the Erdős-Hajnal property
- The $E$-graph and co-$E$
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- Induced embeddings and induced copies of a graph
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
- Homogeneous vertex sets and the homogeneous number $\operatorname{hom}(G)=\max\{\omega(G),\alpha(G)\}$
- The five-vertex path and its complement have the Erdős-Hajnal property
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
26 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
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Introduction and Figure 4 (standard reference, not scraped)