PlanetMath: proof of Wagner's theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (37)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Owner confidence rating: No information about user quality

Entry average rating: No information on entry rating

proof of Wagner's theorem

(Proof)

It is sufficient to prove that the planarity condition given by Wagner's theorem is equivalent to the one given by Kuratowski's theorem, i.e., that a graph has $K_{5}$ or $K_{3,3}$ as a minor, if and only if it has a subgraph homeomorphic to either $K_{5}$ or $K_{3,3}$ . It is not restrictive to suppose that is simple and 2-connected.

First, suppose that has a subgraph homeomorphic to either $K_{5}$ or $K_{3,3}$ . Then there exists $U\subseteq V$ such that the subgraph induced by can be transformed into either $K_{5}$ or $K_{3,3}$ via a sequence of simple subdivisions and simple contractions through vertices of degree 2. Since none of these operations can alter the number of vertices of degree $d\neq 2$ , and neither $K_{5}$ nor $K_{3,3}$ have vertices of degree 2, none of the simple subdivisions is necessary, and the homeomorphic subgraph is actually a minor.

For the other direction, we prove the following.

If has $K_{3,3}$ as a minor, then has a subgraph homeomorphic to $K_{3,3}$ .
If has $K_{5}$ as a minor, then has a subgraph homeomorphic to either $K_{5}$ or $K_{3,3}$ .

Proof of point 1

If has $K_{3,3}$ as a minor, then there exist $U_{1},U_{2},U_{3},W_{1},W_{2},W_{3}\subseteq V$ that are pairwise disjoint, induce connected subgraphs of , and such that, for each and , there exist $u_{i,j}\in U_{i}$ and $w_{i,j}\in W_{j}$ such that $(u_{i,j},w_{i,j})\in E$ . Consequently, for each , there exists a subtree of with three leaves, one leaf in each of the $W_{j}$ 's, and all of its other nodes inside $U_{i}$ ; the situation with the 's is symmetrical.

As a consequence of the handshake lemma, a tree with three leaves is homeomorphic to $K_{1,3}$ : thus, has a subgraph homeomorphic to six copies of $K_{1,3}$ , connected three by three, i.e., to $K_{3,3}$ .

Proof of point 2

If has $K_{5}$ as a minor, then there exist pairwise disjoint $U_{1},\ldots,U_{5}\subseteq V$ that induce connected subgraphs of and such that, for every $i\neq j$ , there exist $u_{i;\{i,j\}}\in U_{i}$ and $u_{j;\{i,j\}}\in U_{j}$ such that $(u_{i;\{i,j\}},u_{j;\{i,j\}})\in E$ . Consequently, for each , there exists a subtree of with four leaves, one leaf in each of the $U_{j}$ 's for $i\neq j$ , and with all of its other nodes inside $U_{i}$ .

As a consequence of the handshake lemma, a tree with three leaves is homeomorphic to either $K_{1,4}$ or two joint copies of $K_{1,3}$ . If all of the trees above are homeomorphic to $K_{1,4}$ , then we can reason as for point 1 and conclude that has a subgraph homeomorphic to $K_{5}$ . Otherwise, fix one tree of the second kind, and “split” it into the two joint copies of $K_{1,3}$ ; color one copy red and one copy blue; color blue the 's linked to the red copy, and red those connected to the blue one. Then a subgraph homeomorphic to $K_{3,3}$ can be constructed similarly to the case of point 1, by “pruning” the other four trees so that they have three leaves, each in a subgraph of a color different than the rest of their vertices.