proof of Wagner’s theorem

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 $G=(V,E)$ 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 $G$ is simple and 2-connected.

First, suppose that $G$ has a subgraph homeomorphic to either $K_5$ or $K_{3,3}$. Then there exists $U\subseteq V$ such that the subgraph induced by $U$ 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\ne 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.

1. If $G$ has $K_{3,3}$ as a minor, then $G$ has a subgraph homeomorphic to $K_{3,3}$.

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

Proof of point 1

If $G$ 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 $G$, and such that, for each $i$ and $j$, 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 $i$, there exists a subtree of $G$ 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 $j$’s is symmetrical.

As a consequence of the handshake lemma, a tree with three leaves is homeomorphic to $K_{1,3}$. Thus, $G$ 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 $G$ has $K_5$ as a minor, then there exist pairwise disjoint $U_1,\mathrm{\dots },U_5\subseteq V$ that induce connected subgraphs of $G$ and such that, for every $i\ne 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 $i$, there exists a subtree $T_i$ of $G$ with four leaves, one leaf in each of the $U_j$’s for $i\ne j$, and with all of its other nodes inside $U_i$.

As a consequence of the handshake lemma, a tree with four 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 $G$ has a subgraph homeomorphic to five copies of $K_{1,4}$, each joint to the others: i.e., to $K_5$. Otherwise, a subgraph homeomorphic to $K_{3,3}$ can be obtained via the following procedure.

1. Choose one of the $T_i$’s which is homeomorphic to two joint copies of $K_{1,3}$, call them $T_{i,r}$ and $T_{i,b}$.

2. Color red the nodes of $T_{i,r}$, except its two leaves, which are colored blue.

3. Color blue the nodes of $T_{i,b}$, except its two leaves, which are colored red.

4. Color blue the nodes of the $T_j$’s containing the leaves of $T_{i,r}$.

5. Color red the nodes of the $T_j$’s containing the leaves of $T_{i,b}$.

6. Remove the edges joining nodes with same color in different $T_j$’s.
   This “prunes” the $T_j$’s so that they have three leaves, each in a subgraph of a color different than the rest of their vertices.

The graph formed by the red and blue nodes, together with the remaining edges, is then isomorphic to $K_{3,3}$.

Title	proof of Wagner’s theorem
Canonical name	ProofOfWagnersTheorem
Date of creation	2014-01-16 17:37:41
Last modified on	2014-01-16 17:37:41
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	14
Author	Ziosilvio (18733)
Entry type	Proof
Classification	msc 05C99