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 nontrivial -free graph is disconnected or has disconnected complement
Statement
Let be a finite simple graph with at least two vertices. If is -free, then is disconnected or is disconnected. Equivalently, no nontrivial -free graph is both connected and anticonnected.
Facts & Assumptions
Given: A finite simple graph with that is -free.
Every finite graph with at least two vertices is connected or anticonnected (Every graph with at least two vertices is connected or anticonnected).
A graph is anticonnected exactly when its complement is connected (Anticonnected graphs and anticonnected components).
Being -free means containing no induced copy of the four-vertex path (-free and -free graphs under the induced-subgraph convention, Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
In a connected graph every vertex has a neighbour, and if is connected then no vertex of is adjacent to all other vertices (Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).
Proof
By [L1], if is disconnected then the first alternative of the Statement already holds. Assume instead that is connected.
Suppose for contradiction that is also anticonnected. Then [L2] makes connected. Choose a vertex . Because is connected and nontrivial, [F1] gives a neighbour of . Because is connected, [F1] also gives a vertex nonadjacent to . Among all pairs with and , choose one for which the distance from to in is minimal. Let be a shortest - path in .
Since and are nonadjacent, one has . A shortest path is induced, so and no nonconsecutive pair among is adjacent. If some with were adjacent to , then would be another neighbour/nonneighbour pair for whose distance is , contradicting the choice in step 1.2. Hence .
The four vertices therefore induce a path: the edges are , , and , while the nonedges are , , and . This is an induced copy of , contradicting [L3].
So a nontrivial -free graph cannot be both connected and anticonnected. Since step 1.1 reduced to the connected case, [L2] shows that whenever is connected, must be disconnected.
Depends on
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- Connected graphs and connected components defined by the existence of vertex paths
- Anticonnected graphs and anticonnected components
- Graph isomorphisms, automorphisms and graph complements
- Every graph with at least two vertices is connected or anticonnected
Used by
Dependency tree · two levels
16 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
- Tung H. Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Exercise 1.1 (standard reference, not scraped)
- Nicolas Bousquet, Aurélie Lagoutte, and Stéphan Thomassé, The Erdős-Hajnal Conjecture for Paths and Antipaths (standard reference, not scraped)