# 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.

alt text http://shrani.si/f/3f/IS/jiP8yvQ/pmin.png

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
• The image seems to be missing. – jeq Dec 28 '17 at 18:44