8
$\begingroup$

I feel sure this must be known, but can I find it??

Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the tree?

If multiple edges are allowed, there might be simply too many faces, and other obstructions are easy to find. But I don't know about simple graphs.

Improve this question
$\endgroup$
1
  • $\begingroup$ Simple triangulations are worth a look. A count indicates that exactly 2 faces must have 2 tree edges, and all the other faces must have 1 tree edge. The corresponding edges in the dual graph (a 3-connected planar cubic graph) are like a perfect matching but have two components of 2 edges or one component of 3 edges. Perhaps this observation can be reversed into a proof? Also, the smallest triangulation without a suitable tree has minimum degree at least 4. $\endgroup$
    – Brendan McKay
    Commented Nov 17, 2012 at 15:56

2 Answers 2

Reset to default
10
$\begingroup$

A triangulation has a spanning tree with the required property if and only if its dual graph has a hamiltonian path (is traceable).

Zamfirescu constructed a 3-regular 3-connected planar non-traceable graph on 88 vertices. The dual of this graph is a triangulation with no spanning tree with required properties.

a reference: Tudor Zamfirescu, Three small cubic graphs with interesting Hamiltonian properties, Journal of Graph Theory, Vol. 4 (1980), 287-292.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, but can you please explain why your first sentence is true? I don't see it in the given reference. $\endgroup$
    – Brendan McKay
    Commented Nov 18, 2012 at 4:35
  • $\begingroup$ Let $T$ be a spanning tree of the triangulation $G$. The edges of the dual graph $G^*$ that do not cross the edges of $T$ form a spanning tree $T^{*}$ in $G^{*}$. Now since $G^{*}$ is $3$-regular, the tree $T$ contains an edge of a face in $G$ if and only if the degree of the corresponding dual vertex is smaller than $3$. Hence the given condition is equivalent to $T^{*}$ being a path. $\endgroup$
    – Jan Kyncl
    Commented Nov 18, 2012 at 6:05
  • $\begingroup$ I get it now. Lovely!! $\endgroup$
    – Brendan McKay
    Commented Nov 18, 2012 at 8:16
0
$\begingroup$

I'm not quite sure I believe my own proof, but, it seems to me that no such graph exists. Not among finite graphs, that is.

Suppose $G$ is an example of a connected, finite plane graph having a spanning tree $T$ such that each face of $G$ has at least one edge in $T$, and suppose that amongst all such examples, $G$ has the least number of edges. Note that $G$ has no separating vertex, for if it did then we could cut at that vertex and get an example with fewer edges. It follows that the boundary $\partial G$ is a circle, so $\partial G$ contains an edge $E$ that is not in $T$. The graph $G - E$ is therefore an example with one fewer edge (and one fewer face), using the same tree $T$. Contradiction.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Suppose $G$ is a triangle. Then $T$ is two of its edges. Doesn't this satisfy the condition that each face of $G$ has at least one edge in $T$? $\endgroup$
    – Joseph O'Rourke
    Commented Nov 17, 2012 at 15:46
  • $\begingroup$ It's a good thing you don't believe your own proof ;). Try $K_4$: a path is a suitable tree. It seems that your descent finishes at a single edge, at which time the argument fails. $\endgroup$
    – Brendan McKay
    Commented Nov 17, 2012 at 15:47
  • 1
    $\begingroup$ Hahahaha. I always tell my students: "Don't forget the base case!" Isn't there a topic on MO somewhere about such "proofs"? $\endgroup$
    – Lee Mosher
    Commented Nov 17, 2012 at 20:16

You must log in to answer this question.

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