# Spanning trees in planar graphs

Is the 3-connected graph(s) on $n$ vertices with the minimum number of spanning trees always planar?

-
I like this question, but I am wondering if you have any particular motivation for this. – Matthew Kahle Oct 14 '10 at 18:44
This question came up when considering an old conjecture of Tutte "Among all 3-connected planar graphs with 2m edges, the graph with the smallest number of spanning trees is the wheel W(m+1)" which is wrong. Then it became interesting to look at a more general version of this question. – utdiscant Oct 14 '10 at 19:17
As stated in my previous comment, that is what Tutte conjectured, but this is wrong, and a counter example can be found at 30 edges. Take a path of length 2 and a path of length 12, then glue each vertex from the short path to each vertex of the long path. This graph is 3-connected, planar and has fewer vertices than the wheel-graph of the same size. – utdiscant Oct 14 '10 at 19:27
It is not true that all minimal 3-connected graphs are planar, look for example at K3,3. – utdiscant Oct 15 '10 at 2:07
The "other post" that Gwyn mentioned seems to be mathoverflow.net/questions/42189/…;, and the paper is Fisher, Fraughnaugh, Langley, "P_3 connected graphs of minimal size". Unfortunately, P_3 connectivity seems to be rather different from standard 3-connectivity. – Dylan Thurston Oct 16 '10 at 21:11

This is therefore not an answer anymore but rather an extended comment for the case $n=11.$