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.
Relative to a complete nonedge pair in a co--free graph, every one-sided vertex is pure to an induced
Statement
Let be co--free. If nonadjacent are complete to an induced copy of and , then is complete or anticomplete to that copy of .
Facts & Assumptions
Given: and a labeled induced as in the Statement.
The labeled has rim , hub complete to the rim, and leaves adjacent only to (The graphs ).
On any induced path to which is mixed and whose exterior vertices are , the preceding path-run lemma forbids two consecutive nonneighbours and three consecutive neighbours (Relative to a complete nonedge pair in a co--free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours).
Proof
Suppose is mixed on the . If is complete to the rim and some is a nonedge, then is mixed on the induced path and has three consecutive neighbours there, contrary to [F2]. Thus is adjacent to every . If failed, induces co-; hence holds and is complete to , a contradiction.
If is anticomplete to the rim and some is an edge, then is mixed on with two consecutive nonneighbours, contrary to [F2]. Thus every is a nonedge. If were an edge, then would be mixed on with two consecutive nonneighbours, again contrary to [F2]. Hence is a nonedge, so is anticomplete to , also a contradiction.
It remains that is mixed on the rim. Any cyclic run of two rim nonneighbours or three rim neighbours, together with a vertex of the opposite adjacency supplied by mixedness, lies in an induced rim subpath to which [F2] applies. Thus the two run restrictions force, up to cyclic relabeling, . If were a nonedge, then would be mixed on with two consecutive nonneighbours; if were a nonedge, then would be mixed on with three consecutive neighbours. Hence [F2] gives ; then induces co-, impossible.
Every possible rim relation contradicts mixedness, so is pure to the induced .
Depends on
- Relative to a complete nonedge pair in a co-$E$-free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours
- The graphs $H_0,H_1,\ldots,H_5$
- The $E$-graph and co-$E$
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
Used by
Dependency tree · two levels
8 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
- Huang, Ju, and Zhou, Erdős-Hajnal beyond the five-vertex path, Claim 6.4.2 (standard reference, not scraped)