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.
In an edge-maximal graph with no or subdivision, a minimum proper separation of order at most two has an adjacent two-vertex separator and edge-maximal sides
Statement
Let be edge-maximal among graphs containing no subdivision of or . A proper separation is a pair with , neither contained in the other, and no edge between and ; its separator is and its order is the size of that set. If has minimum order among proper separations and that order is at most two, then its separator has two vertices , the edge belongs to , and each induced side is itself edge-maximal without either subdivision. Vertex cuts and induced subgraphs are Vertex cuts, edge cuts, vertex connectivity and edge connectivity , with conventions for complete and one-vertex graphs and Subgraphs, induced subgraphs and spanning subgraphs; obstruction terminology agrees with A graph has a or minor exactly when it has a subdivision of or as a subgraph.
Facts & Assumptions
Given: Such and a minimum proper separation with separator .
A graph has a or minor exactly when it contains a subdivision of or (A graph has a or minor exactly when it has a subdivision of or as a subgraph).
Proof
Minimum order implies every vertex of has a neighbour in every component on either proper side; otherwise deleting that vertex from would give a smaller separator. Direct inspection shows that deleting any total of at most two vertices or edges from or leaves all surviving vertices connected. Consequently a subdivision of either obstruction cannot have branch vertices on both proper sides of a separation of order at most two: after suppressing subdivided paths, separator vertices internal to those paths delete obstruction edges, while separator branch vertices delete obstruction vertices. Its intersection with the side having no branch vertex is therefore at most one path replacing an obstruction edge.
If were empty, add an edge across the two sides. A created subdivision would have to use , but deleting one edge from a subdivision of either obstruction leaves its branch vertices connected, whereas they would lie in two components of . If , choose neighbours of on opposite sides and add . Delete and from a created subdivision and suppress its remaining subdivided paths. By the deletion observation in step 1.1, all surviving branch vertices, and hence all branch vertices before restoring a possible branch vertex , lie on one side. The branch-free excursion through the other side runs from one endpoint of to ; replace it together with by the existing edge or on the branch-vertex side. This gives the same forbidden subdivision in . Edge maximality rules out both cases, so .
If were absent, add it. Any resulting forbidden subdivision can replace by an - path through the proper side without its branch vertices, as described in step 1.1, again yielding the subdivision in . Therefore .
Finally add any missing edge within one induced side. A resulting obstruction either lies in that side, proving its edge maximality, or uses the other side only as an - path; replace that path by the existing edge . An obstruction wholly in the other side was already in . Hence each side is edge-maximal and obstruction-free.
Depends on
- A graph has a $K_5$ or $K_{3,3}$ minor exactly when it has a subdivision of $K_5$ or $K_{3,3}$ as a subgraph
- Vertex cuts, edge cuts, vertex connectivity $\kappa(G)$ and edge connectivity $\lambda(G)$, with conventions for complete and one-vertex graphs
- Subgraphs, induced subgraphs and spanning subgraphs
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 19 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., Lemma 4.4.4 (standard reference, not scraped)