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 has or as a minor, if and only if it has a subgraph homeomorphic to either or . It is not restrictive to suppose that is simple and 2-connected.
First, suppose that has a subgraph homeomorphic to either or . Then there exists such that the subgraph induced by can be transformed into either or 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 , and neither nor 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 as a minor, then has a subgraph homeomorphic to .
If has as a minor, then has a subgraph homeomorphic to either or .
Proof of point 1
If has as a minor, then there exist that are pairwise disjoint, induce connected subgraphs of , and such that, for each and , there exist and such that . Consequently, for each , there exists a subtree of with three leaves, one leaf in each of the ’s, and all of its other nodes inside ; the situation with the ’s is symmetrical.
Proof of point 2
If has as a minor, then there exist pairwise disjoint that induce connected subgraphs of and such that, for every , there exist and such that . Consequently, for each , there exists a subtree of with four leaves, one leaf in each of the ’s for , and with all of its other nodes inside .
As a consequence of the handshake lemma, a tree with four leaves is homeomorphic to either or two joint copies of . If all of the trees above are homeomorphic to , then has a subgraph homeomorphic to five copies of , each joint to the others: i.e., to . Otherwise, a subgraph homeomorphic to can be obtained via the following procedure.
Choose one of the ’s which is homeomorphic to two joint copies of , call them and .
Color red the nodes of , except its two leaves, which are colored blue.
Color blue the nodes of , except its two leaves, which are colored red.
Color blue the nodes of the ’s containing the leaves of .
Color red the nodes of the ’s containing the leaves of .
Remove the edges joining nodes with same color in different ’s.
This “prunes” the ’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 .
|Title||proof of Wagner’s theorem|
|Date of creation||2014-01-16 17:37:41|
|Last modified on||2014-01-16 17:37:41|
|Last modified by||Ziosilvio (18733)|