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

  • 1
    $\begingroup$ What are some examples of such 3c-min-span graphs? Presumably you know some classes that achieve the min... $\endgroup$ Oct 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$
    – utdiscant
    Oct 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 1


Are the minimally 3-connected graphs (edge removal pushes you into a 2-connected graph) the same as the class of 3-connected graphs with the minimal number of spanning trees? There is a nice classification of the minimal 3-connected graphs (or maximal not-3-connected 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 3-connected graphs inside a paper by David Fisher, Kathryn Fraughnaugh, and Larry Langley which could help ["3-connected graphs of minimal size".] At the very least, they note that all 3-connected graphs on n vertices have at least 3/2(n-2) edges, and produce graphs achieving this bound. All of your graphs with the minimal number of spanning trees must be one of these minimal 3-connected graphs (as if your hypothetical "minimal spanning tree" graph wasn't also a minimal 3-connected graph, removing edges to a minimal 3-connected graph would reduce the number of spanning trees.)

  • $\begingroup$ It is true that the 3-connected graph(s) with the minimum number of spanning trees must be found among the 3-connected 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 3-connected graphs have more than ceil(3n/2) edges. For instance the Wheel Graph on 6 vertices is a minimal 3-connected graph, but has 10 edges. $\endgroup$
    – utdiscant
    Oct 15, 2010 at 1:57
  • $\begingroup$ Also, I can't seem to find the paper ["3-connected graphs of minimal size".] which you are referring too, do you have a link? $\endgroup$
    – utdiscant
    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$
    – JBL
    Oct 15, 2010 at 2:31
  • $\begingroup$ Yeah, that's a good point. Since the complex of not 3-connected graphs is homotopic to a wedge of spheres of the same dimension, I was under the impression that all of the minimal 3-connected 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

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.