Application of Wagner’s Theorem

Testing whether or not a graph is planar is an important aspect of graph theory. Wagner’s Theorem provides a characterization of planar graphs based on graph minors. It is a nice alternative to Kuratowski’s Theorem. Euler’s formula and graph coloring are both necessary conditions for a graph to be planar, and so the associated tests are non-deterministic. That is, just because a graph satisfy Euler’s formula (or a corollary) does not mean it is planar. Similarly, the graph is non-planar, but it is two-colorable.

Kuratowski’s Theorem states that a graph is planar if and only if no subdivision of or are contained in .

Wagner’s Theorem relies instead on graph minors. It states that a graph is planar if and only if does not contain or as minors. A graph minor is constructed from by contracting selected edges, deleting selected edges, and deleting selected vertices.

In order to demonstrate Wagner’s Theorem, the following proposition will be proven.

Proposition: Let be a simple, connected bipartite graph with vertices each of degree . Then is non-planar.

Proof: To be proven directly. By the Handshake Lemma, there exist edges in . As is three regular, the only potential partition sizes are or . As configuration uses only edges, and a configuration only uses edges. So the two partitions must each contain vertices. We now prove the following Lemma.

Lemma 1: Let be in the same partition. Then and share a common neighbor.

This property follows by the pigeonhole principle. By extremality, let be adjacent to in the second partition and adjacent to in the second partition. As is -regular, both must have one more edge. If (without loss of generality) is adjacent to one of ‘s neighbors, then we are done. Otherwise, by extremality, suppose is adjacent to . Now by the pigeonhole principle, must share one neighbor with , completing the proof of this lemma.

Lemma will now be used to show the existence of a . Consider . They share a common neighbor by Lemma . Let be the neighbor of . By Lemma , and some other vertex in its partition. Call this vertex . And so we have a path . Using Lemma again, and some other vertex in the same partition must share as a neighbor. Applying Lemma once more yields a vertex adjacent to both , completing the six-cycle.

Now construct into a instance. This leaves five remaining edges, which form a perfect matching on . Observe that three vertices in one partition cover the other partition. That is, selecting any three vertices in one partition, there exist edges to all the vertices in the second partition only using the edges of the selected vertices in the first partition. Thus, consider each vertex in the first partition. Contract all three edges incident to . Thus, is adjacent to all other vertices in partition one. And so contracting the second partition into the first partition produces a minor. So by Wagner’s Theorem, is not planar. QED.

Remark Observe that satisfies the corollary to Euler’s formula for bipartite graphs. That is, planar bipartite graphs satisfy the condition that . There are vertices and edges in , and so satisfies this corollary. This is a good example of Euler’s formula being a necessary but not sufficient condition for planarity.