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\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.

1. 1.

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

2. 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},\ldots,U_{5}\subseteq V$ that induce connected subgraphs of $G$ 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 $i$, there exists a subtree $T_{i}$ of $G$ 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 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. 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. 2.

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

3. 3.

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

4. 4.

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

5. 5.

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

6. 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}$.

References

• 1 Geir Agnarsson, Raymond Greenlaw. Graph Theory: Modeling, Applications and Algorithms. Prentice Hall, 2006.
Title proof of Wagner’s theorem ProofOfWagnersTheorem 2014-01-16 17:37:41 2014-01-16 17:37:41 Ziosilvio (18733) Ziosilvio (18733) 14 Ziosilvio (18733) Proof msc 05C99