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 -graph and Bird singleton families are leaf-reducible
Statement
The singleton forbidden families and are leaf-reducible. In , deleting the leaf attached to the middle vertex gives . In Bird, deleting the added leaf gives the bull. Both reduced singleton families have the Erdős-Hajnal property.
Facts & Assumptions
Given: The -graph on , the Bird graph on , and the bull on .
The -graph has edge set and co- is its complement (The -graph and co-).
The Bird graph has edge set and co-Bird is its complement (The Bird graph and co-Bird).
The bull has vertex set and edge set (The bull graph).
The path graph has vertices and edges for , and no others (Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
A finite family is leaf-reducible when some has a leaf and the modified family has the Erdős-Hajnal property in the family sense (Leaf-reducible finite graph families).
A vertex of degree one is a leaf; deletion is the subgraph induced by (Trees, forests, leaves and isolated vertices, Subgraphs, induced subgraphs and spanning subgraphs).
A graph isomorphism is a bijection preserving adjacency and nonadjacency, and an induced embedding of in is an injection preserving adjacency and nonadjacency on distinct pairs (Graph isomorphisms, automorphisms and graph complements, Induced embeddings and induced copies of a graph).
A graph is -free when it has no induced copy of , and -free means -free for every (-free and -free graphs under the induced-subgraph convention).
The graph has the Erdős-Hajnal property (The five-vertex path and its complement have the Erdős-Hajnal property).
The bull graph has the Erdős-Hajnal property (The bull graph has the Erdős-Hajnal property).
A graph has the Erdős-Hajnal property when the hereditary class of -free graphs has an Erdős-Hajnal constant, and the same terminology applies to a finite family through its class of family-free graphs (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).
Proof
In the only edge incident with is , by [L1]. Hence has degree one and is a leaf, and is the induced subgraph on with exactly the four edges .
In Bird the only edge incident with is , by [L2]. Hence has degree one and is a leaf, and is the induced subgraph on with edge set , which is exactly the bull of [L3].
Take and the member with the leaf of step 1.2. Then is the bull by step 1.2, so the modified family of [L5] is the singleton , whose Erdős-Hajnal property is [L10] read through the family terminology of [L11]; both phrases describe the same class of bull-free graphs. Hence is leaf-reducible.
The map for is a bijection from onto whose four edges of [L4] correspond to the four edges listed in step 1.1, and no other pairs are edges on either side. A bijection matching adjacency and nonadjacency is an isomorphism by [L7], so .
Consequently a finite graph is -free if and only if it is -free: composing an induced embedding of in with the inverse of the isomorphism of step 2.2 yields an induced embedding of in , and composing an induced embedding of with that isomorphism yields an induced embedding of .
By [L9] the class of -free graphs has an Erdős-Hajnal constant; step 3.1 identifies it with the class of -free graphs, so that class also has a constant, and [L11] makes the singleton family a family with the Erdős-Hajnal property.
Take and the member with the leaf of step 1.1. Then , so the modified family of [L5] is , which has the Erdős-Hajnal property by step 4.1. Hence is leaf-reducible.
The two singleton families are leaf-reducible, the deleted graph is in the case and the bull in the Bird case, and the reduced singleton families and have the Erdős-Hajnal property by steps 2.1 and 4.1. These are all the assertions of the statement.
Remarks
- The two deletions are exactly the source's Section 2.1 observation that and Bird are leaf-reducible: is the pendant vertex of at the middle of the , and is the extra pendant vertex attached at the horn of the bull inside Bird.
- No Choice. Every object here is finite and every step is a finite adjacency check or a citation of a published finite result; no selection from a family of nonempty sets occurs.
Depends on
- Leaf-reducible finite graph families
- The $E$-graph and co-$E$
- The Bird graph and co-Bird
- The bull graph
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- Subgraphs, induced subgraphs and spanning subgraphs
- Trees, forests, leaves and isolated vertices
- Graph isomorphisms, automorphisms and graph complements
- Induced embeddings and induced copies of a graph
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
- The five-vertex path and its complement have the Erdős-Hajnal property
- The bull graph has the Erdős-Hajnal property
Used by
Dependency tree · two levels
29 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, Section 2.1 (standard reference, not scraped)