4
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The existence of $C$ for a planar triangulation follows immediately from en.wikipedia.org/wiki/Petersen's_theorem $\endgroup$
    – David Eppstein
    Commented Aug 15, 2014 at 23:21
  • 1
    $\begingroup$ @DavidEppstein: Could you please spell out a few steps of "follows immediately"? $\endgroup$
    – Joseph O'Rourke
    Commented Aug 15, 2014 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
    Commented Aug 15, 2014 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
    Commented Aug 15, 2014 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
    Commented Aug 16, 2014 at 5:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .