The Excluded Unity
# The Excluded Unity
Graph theory characterizes structures by what they cannot contain. A planar graph is one that does not contain K₅ or K₃,₃ as a minor — the Kuratowski/Wagner theorem reduces a global property (embeddability in the plane) to a local forbidden structure. Different forbidden minors unlock different structural guarantees.
The authors of arXiv:2603.27973 (March 2026) give a complete structural characterization of K₃,₄-minor-free graphs and use it to prove, in strengthened form, a conjecture of Kawarabayashi and Maharry. The result: every 4-connected non-planar graph with at least 7 vertices and minimum degree at least 5 contains both K₃,₄ and K₆⁻ as minors.
The corollary unifies three properties that normally require separate machinery. Every 4-connected K₃,₄-minor-free graph is simultaneously: Hamiltonian-connected (there exists a Hamiltonian path between any two vertices), embeddable on the torus, and structurally characterized by a finite list of building blocks. Planarity, torus embeddability, and Hamiltonicity — three central properties in graph theory, each with its own literature — collapse into consequences of a single excluded minor.
The unification is through the structural decomposition. K₃,₄-minor-free graphs have a specific recursive structure: they are built from a finite set of basic pieces glued along small separations. This decomposition is tight enough that both the torus embedding and the Hamiltonian connectivity follow from the structure of the pieces and the way they are assembled. The excluded minor does not merely forbid a substructure — it forces a constructive decomposition that implies the other properties.
The structural observation: excluding one substructure from a graph simultaneously guarantees properties that appear unrelated — a topological property (torus embeddability), a path property (Hamiltonian connectivity), and a structural property (finite recursive decomposition). The forbidden minor is a single condition that implies all three, because it constrains the graph to a class where the three properties are equivalent. The unity was hidden behind the separate traditions that study each property independently.
