# 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

Edit. As it turned out I was not using the right switch for plantri.

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

As it turns out the minimal number of spanning trees of a 3-connected planar graph of order 11 is 3965 and is attained by the graph on the figure bellow.

As for the non-planar 3-connected graph I am yet to compute the answer. I'll post the result here as soon as it gets computed.

-
What about the following graph imgur.com/Eow3L6L which have 3965 spanning trees? –  utdiscant Feb 7 '13 at 11:26
Weird. I'll try to run the program again and see why the proposed graph is not found. It clearly looks like a counterexample to the stated answer! –  Jernej Feb 7 '13 at 12:46