proof of Wagner’s theorem

It is sufficient to prove thatthe planarity condition given by Wagner’s theoremis 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 subgraphhomeomorphic 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 subgraphhomeomorphic 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 subdivisionsand simple contractions through vertices of degree 2.Since none of these operationscan 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 tofive 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$’swhich 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$’scontaining the leaves of $T_{i,r}$.

5. Color red the nodes of the $T_j$’scontaining 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}$.