Spanning trees of plane graphs containing an edge of every face 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.
 A: 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.
A: 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.
