Is the number of edges in the 3connected graph with the minimum number of spanning trees always $\lceil {\frac{3}{2}}n\rceil$?

1$\begingroup$ What are some examples of such 3cminspan graphs? Presumably you know some classes that achieve the min... $\endgroup$– Joseph O'RourkeOct 14, 2010 at 19:40

$\begingroup$ It seems there are no classes which achieve the minimum always. An example of a class which achieve a low number of spanning trees are Prism Graphs, but they do not always have the minimum number of spanning trees. $\endgroup$– utdiscantOct 14, 2010 at 20:50

$\begingroup$ For what values of n do you know this to be true? $\endgroup$– j.c.Oct 15, 2010 at 0:18
1 Answer
Are the minimally 3connected graphs (edge removal pushes you into a 2connected graph) the same as the class of 3connected graphs with the minimal number of spanning trees? There is a nice classification of the minimal 3connected graphs (or maximal not3connected graphs, I forget which direction he does it in) in Jonsson's book "Simplicial Complexes of Graphs".
I think there's also a classification of minimal 3connected graphs inside a paper by David Fisher, Kathryn Fraughnaugh, and Larry Langley which could help ["3connected graphs of minimal size".] At the very least, they note that all 3connected graphs on n vertices have at least 3/2(n2) edges, and produce graphs achieving this bound. All of your graphs with the minimal number of spanning trees must be one of these minimal 3connected graphs (as if your hypothetical "minimal spanning tree" graph wasn't also a minimal 3connected graph, removing edges to a minimal 3connected graph would reduce the number of spanning trees.)

$\begingroup$ It is true that the 3connected graph(s) with the minimum number of spanning trees must be found among the 3connected graphs with the minimal number of edges, but this is not enough to draw a conclusion, since it is easy to find examples showing that minimal 3connected graphs have more than ceil(3n/2) edges. For instance the Wheel Graph on 6 vertices is a minimal 3connected graph, but has 10 edges. $\endgroup$ Oct 15, 2010 at 1:57

$\begingroup$ Also, I can't seem to find the paper ["3connected graphs of minimal size".] which you are referring too, do you have a link? $\endgroup$ Oct 15, 2010 at 2:01

$\begingroup$ The actual title appears to be "P_3  connected graphs of minimal size" in Ars Combinatorica. I found this by putting one of the author's names into my favorite search engine. This led me to the personal website of the author, which included a CV, which included a list of papers. (MathSciNet would have been even quicker.) $\endgroup$– JBLOct 15, 2010 at 2:31

$\begingroup$ Yeah, that's a good point. Since the complex of not 3connected graphs is homotopic to a wedge of spheres of the same dimension, I was under the impression that all of the minimal 3connected graphs were of the same size  not the case. The critical graphs left over after an appropriately chosen discrete Morse matching are though... Do you have these graphs classified for small n? $\endgroup$ Oct 15, 2010 at 5:00