Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Brendan McKay Nov 17 '12 at 15:56

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
    
Thanks, but can you please explain why your first sentence is true? I don't see it in the given reference. –  Brendan McKay Nov 18 '12 at 4:35
    
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. –  Jan Kyncl Nov 18 '12 at 6:05
    
I get it now. Lovely!! –  Brendan McKay Nov 18 '12 at 8:16

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.

share|improve this answer
1  
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$? –  Joseph O'Rourke Nov 17 '12 at 15:46
    
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. –  Brendan McKay Nov 17 '12 at 15:47
1  
Hahahaha. I always tell my students: "Don't forget the base case!" Isn't there a topic on MO somewhere about such "proofs"? –  Lee Mosher Nov 17 '12 at 20:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.