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 Petersen graph is nonplanar by an explicit subdivision of after deleting one vertex
Example
Deleting one vertex from the Petersen graph exposes a subdivision of .
Facts & Assumptions
Given: Label a Petersen vertex by a two-element subset of , with adjacency exactly when labels are disjoint, as in The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint.
A finite graph is planar exactly when it contains neither a subdivision of nor a subdivision of (Kuratowski–Wagner theorem: a finite graph is planar exactly when it has neither a nor a minor, equivalently neither subdivision).
Two Petersen vertices are adjacent exactly when their two-element labels are disjoint (The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint).
Verification
Delete the vertex . Take the branch classes and . The six direct branch connections are to , to , and to . The remaining three are the paths , , and .
Every consecutive pair in the displayed list has disjoint labels, so it is an edge by [F1]. The internal vertices are distinct and are not branch vertices; all other listed connections are single edges. Thus the nine paths are internally disjoint and form a subdivision, in the sense of Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors, of with branch classes and . This subdivision lies in a subgraph of the Petersen graph, so [L1] proves that the Petersen graph is nonplanar.
Depends on
- Kuratowski–Wagner theorem: a finite graph is planar exactly when it has neither a $K_5$ nor a $K_{3,3}$ minor, equivalently neither subdivision
- The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
Used by
Nothing in the library uses this result yet.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 35 results over 11 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- R. Diestel, Graph Theory, 6th ed., Section 4.4 (standard reference, not scraped)