Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 K5K_5 or K3,3K_{3,3} subdivision, a minimum proper separation of order at most two has an adjacent two-vertex separator and edge-maximal sides

Statement

Let GG be edge-maximal among graphs containing no subdivision of K5K_5 or K3,3K_{3,3}. A proper separation is a pair (V1,V2)(V_1,V_2) with V1V2=V(G)V_1\cup V_2=V(G), neither ViV_i contained in the other, and no edge between V1V2V_1\setminus V_2 and V2V1V_2\setminus V_1; its separator is V1V2V_1\cap V_2 and its order is the size of that set. If (V1,V2)(V_1,V_2) has minimum order among proper separations and that order is at most two, then its separator has two vertices x,yx,y, the edge xyxy belongs to GG, and each induced side G[Vi]G[V_i] is itself edge-maximal without either subdivision. Vertex cuts and induced subgraphs are Vertex cuts, edge cuts, vertex connectivity κ(G)\kappa(G) and edge connectivity λ(G)\lambda(G), with conventions for complete and one-vertex graphs and Subgraphs, induced subgraphs and spanning subgraphs; obstruction terminology agrees with A graph has a K5K_5 or K3,3K_{3,3} minor exactly when it has a subdivision of K5K_5 or K3,3K_{3,3} as a subgraph.

Facts & Assumptions

Given: Such GG and a minimum proper separation (V1,V2)(V_1,V_2) with separator S=V1V2S=V_1\cap V_2.

[L1]

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

Proof

technique · direct
1.1

Minimum order implies every vertex of SS has a neighbour in every component on either proper side; otherwise deleting that vertex from SS would give a smaller separator. Direct inspection shows that deleting any total of at most two vertices or edges from K5K_5 or K3,3K_{3,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 SS were empty, add an edge ee across the two sides. A created subdivision would have to use ee, but deleting one edge from a subdivision of either obstruction leaves its branch vertices connected, whereas they would lie in two components of GG. If S={v}S=\{v\}, choose neighbours a,ba,b of vv on opposite sides and add e=abe=ab. Delete ee and vv 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 vv, lie on one side. The branch-free excursion through the other side runs from one endpoint of ee to vv; replace it together with ee by the existing edge avav or bvbv on the branch-vertex side. This gives the same forbidden subdivision in GG. Edge maximality rules out both cases, so S={x,y}S=\{x,y\}.

step 1.1
3.1

If xyxy were absent, add it. Any resulting forbidden subdivision can replace xyxy by an xx-yy path through the proper side without its branch vertices, as described in step 1.1, again yielding the subdivision in GG. Therefore xyE(G)xy\in 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 xx-yy path; replace that path by the existing edge xyxy. An obstruction wholly in the other side was already in GG. Hence each side is edge-maximal and obstruction-free.

step 1.1step 3.1L1

Depends on

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