10
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ I like this question, but I am wondering if you have any particular motivation for this. $\endgroup$ Oct 14, 2010 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, 2010 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, 2010 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, 2010 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$ Oct 16, 2010 at 21:11

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What about the following graph imgur.com/Eow3L6L which have 3965 spanning trees? $\endgroup$
    – utdiscant
    Feb 7, 2013 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, 2013 at 12:46
  • $\begingroup$ The image seems to be missing. $\endgroup$
    – jeq
    Dec 28, 2017 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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