# Contracting a planar graph to a (multiply-edged)-tree

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, and if one ignores parallel edges, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar graphs which admit such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Let $G$ be the dual to the Tutte graph. Then $G$ is a planar triangulation. Towards a contradiction, suppose that $G$ has a set of edges $C$ such that $G / C$ is a thick-tree $T$ (a tree with multiple-edges). Note that $C$ must contain at least one edge from each face of $G$, since otherwise $T$ will contain a triangle. On the other hand, $C$ cannot contain more than one edge from each face, since otherwise $T$ will contain a loop. Thus, $C$ contains exactly one edge from each face of $G$. By Euler's formula, this implies that $G / C$ has only two vertices. In particular, $(G / C)^*$ is Hamiltonian. Since contraction and deletion are dual operations, we have $(G / C)^*=G^* \backslash C$. This implies that the Tutte graph has a Hamilton cycle, which is a contradiction.
• The existence of $C$ for a planar triangulation follows immediately from en.wikipedia.org/wiki/Petersen's_theorem – David Eppstein Aug 15 '14 at 23:21
• Your condition "each face contains exactly one edge" is the same as requiring that $C$ forms a matching in the dual graph. For a maximal planar graph, the dual is 3-regular (every face is a triangle) and 3-connected. Petersen also requires 3-regularity but a weaker connectivity condition (no bridges), and with those conditions guarantees that a perfect matching exists. – David Eppstein Aug 15 '14 at 23:39