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

$\begingroup$ I like this question, but I am wondering if you have any particular motivation for this. $\endgroup$ – Matthew Kahle Oct 14 '10 at 18:44

$\begingroup$ This question came up when considering an old conjecture of Tutte "Among all 3connected 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. $\endgroup$ – utdiscant Oct 14 '10 at 19:17

2$\begingroup$ 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 3connected, planar and has fewer vertices than the wheelgraph of the same size. $\endgroup$ – utdiscant Oct 14 '10 at 19:27

1$\begingroup$ It is not true that all minimal 3connected graphs are planar, look for example at K3,3. $\endgroup$ – utdiscant Oct 15 '10 at 2:07

1$\begingroup$ 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 3connectivity. $\endgroup$ – 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 3connected planar graph of order 11 is 3965 and is attained by the graph on the figure bellow.
alt text http://shrani.si/f/3f/IS/jiP8yvQ/pmin.png
As for the nonplanar 3connected graph I am yet to compute the answer. I'll post the result here as soon as it gets computed.

1$\begingroup$ What about the following graph imgur.com/Eow3L6L which have 3965 spanning trees? $\endgroup$ – utdiscant Feb 7 '13 at 11:26

$\begingroup$ 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! $\endgroup$ – Jernej Feb 7 '13 at 12:46
