Is the 3-connected 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 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. $\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 3-connected, planar and has fewer vertices than the wheel-graph of the same size. $\endgroup$ – utdiscant Oct 14 '10 at 19:27
  • 1
    $\begingroup$ It is not true that all minimal 3-connected 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 3-connectivity. $\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 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.