Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-11
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 K5 or K3,3 subdivision, a minimum proper separation of order at most two has an adjacent two-vertex separator and edge-maximal sides

Statement

Let G be edge-maximal among graphs containing no subdivision of K5 or K3,3. A proper separation is a pair (V1,V2) with V1∪V2=V(G), neither Vi contained in the other, and no edge between V1∖V2 and V2∖V1; its separator is V1∩V2 and its order is the size of that set. If (V1,V2) has minimum order among proper separations and that order is at most two, then its separator has two vertices x,y, the edge xy belongs to G, and each induced side G[Vi] is itself edge-maximal without either subdivision. Vertex cuts and induced subgraphs are Vertex cuts, edge cuts, vertex connectivity κ(G) and edge connectivity λ(G), with conventions for complete and one-vertex graphs and Subgraphs, induced subgraphs and spanning subgraphs; obstruction terminology agrees with A graph has a K5 or K3,3 minor exactly when it has a subdivision of K5 or K3,3 as a subgraph.

Facts & Assumptions

Given: Such G and a minimum proper separation (V1,V2) with separator S=V1∩V2.

[L1]

A graph has a K5 or K3,3 minor exactly when it contains a subdivision of K5 or K3,3 (A graph has a K5 or K3,3 minor exactly when it has a subdivision of K5 or K3,3 as a subgraph).

Proof

technique · direct
1.1

Minimum order implies every vertex of S has a neighbour in every component on either proper side; otherwise deleting that vertex from S would give a smaller separator. Direct inspection shows that deleting any total of at most two vertices or edges from K5 or K3,3 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.

givenL1
2.1

If S were empty, add an edge e across the two sides. A created subdivision would have to use e, but deleting one edge from a subdivision of either obstruction leaves its branch vertices connected, whereas they would lie in two components of G. If S={v}, choose neighbours a,b of v on opposite sides and add e=ab. Delete e and v 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 v, lie on one side. The branch-free excursion through the other side runs from one endpoint of e to v; replace it together with e by the existing edge av or bv on the branch-vertex side. This gives the same forbidden subdivision in G. Edge maximality rules out both cases, so S={x,y}.

step 1.1
3.1

If xy were absent, add it. Any resulting forbidden subdivision can replace xy by an x-y path through the proper side without its branch vertices, as described in step 1.1, again yielding the subdivision in G. Therefore xy∈E(G).

step 1.1step 2.1L1
4.1

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 x-y path; replace that path by the existing edge xy. An obstruction wholly in the other side was already in G. Hence each side is edge-maximal and obstruction-free.

step 1.1step 3.1L1∎

Depends on

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