3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

A counterexample is the planar dual to the Tutte graph. Most of the credit goes to David Eppstein (see the comments below)

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The existence of $C$ for a planar triangulation follows immediately from en.wikipedia.org/wiki/Petersen's_theorem $\endgroup$ – David Eppstein Aug 15 '14 at 23:21
  • 1
    $\begingroup$ @DavidEppstein: Could you please spell out a few steps of "follows immediately"? $\endgroup$ – Joseph O'Rourke Aug 15 '14 at 23:34
  • 4
    $\begingroup$ 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. $\endgroup$ – David Eppstein Aug 15 '14 at 23:39
  • 1
    $\begingroup$ @TonyHuynh: you keep finding the mistakes in your proposed counterexamples and removing them again faster than I can leave comments about them! Perhaps it will save you some effort if I observe that any counterexample has to be non-dual-Hamiltonian. Because if a Hamiltonian cycle exists in the dual, then by contracting both sides of it you can get down to a single multi-edge with no self-loops. $\endgroup$ – David Eppstein Aug 15 '14 at 23:55
  • 1
    $\begingroup$ Your latest edit (the one showing that a dual matching in a maximal planar graph works only when the contraction has only two vertices) seems like you're very close to a counterexample. The remaining edges must be dual to a Hamiltonian cycle, I think, so you get a counterexample whenever your maximal planar graph is not dual Hamiltonian. Non-dual-Hamiltonian triangulations do exist; see en.wikipedia.org/wiki/Tait's_conjecture $\endgroup$ – David Eppstein Aug 16 '14 at 5:20

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.