This question is about simple undirected planar graphs without loops. Starting with a planar graph ${\cal G}_0$ in which all vertex degrees are even we perform edge contractions, thus obtaining new graphs that are minors of ${\cal G}_0$ (and that are therefore also planar). The question is whether every maximal planar graph ${\cal G}_1$ (with arbitrary even and/or odd vertex degrees) can be obtained in that way as a minor of some appropriate ${\cal G}_0$ (clearly ${\cal G}_0$ will in general be different for different ${\cal G}_1$)? Also, if every ${\cal G}_1$ can be obtained in that way, then given a ${\cal G}_1$ how do I actually construct a ${\cal G}_0$ and a corresponding contraction?

Trivially, if ${\cal G}_1$ itself only has even vertex degrees, then we can just choose ${\cal G}_0={\cal G}_1$ (a graph is a minor of itself). The question is really about ${\cal G}_1$ that also have odd vertex degrees.

(I am only interested in maximal planar ${\cal G}_1$, but maximality may not actually be important for this question - but I am not sure)


Inspired by your correction of my earlier answer, define the operation of uncontracting an edge $(u, v)$ as inserting a new vertex $w$ in the interior of one of the faces of the edge and adding edges $(u, w)$ and $(v, w)$. This inserts one vertex of even degree and toggles the parity of $u$ and $v$. Contracting $(u, w)$ or $(v, w)$ restores the original graph.

By the handshake lemma, the number of odd degree vertices in a connected component is even. Therefore the following algorithm gives a graph which can be edge-contracted to $G$:

If $G$ has no odd vertices, we're done. Otherwise uncontract each edge along a path between two odd vertices, reducing the number of odd vertices by two, and recurse.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.