Welcome to MathOverflow

Question

7

2

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.

flag	asked Nov 17 at 9:31 Brendan McKay 9,120●1●13●33

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 at 15:56

Jan Kyncl · Answer 1 · 2012-11-18 02:38:51Z UTC

8

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.

answered Nov 18 at 2:38

Jan Kyncl
421●5

	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 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 at 6:05
	I get it now. Lovely!! – Brendan McKay Nov 18 at 8:16

Lee Mosher · Answer 2 · 2012-11-17 15:22:58Z UTC

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.

spanning trees of plane graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.