# Can every maximal planar graph be obtained as a minor of a planar graph with only even vertex degrees?

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.