The passage quoted below is from "The number of spanning trees of a graph" by Jianxi Li, Wai Chee Shiu, and An Chang, Applied Mathematics Letters 23.3 (2010): 286-290, DOI:10.1016/j.aml.2009.10.006, MR2565192, Zbl 1227.05125.

Could someone clearly explain the proof of the inequality on the number of spanning trees of a graph $G$ in this passage?

This inequality seems to contradict Cayley's formula for the number of spanning trees of the complete graph. I tested a complete graph $G=K_5$. This formula gave me $121$ as an upper bound for the number of spanning trees while Cayley's gave me $125$. I am not able to figure out how it went wrong.

enter image description here enter image description here

Could someone provide some insights?

  • 2
    $\begingroup$ I agree with you that the formula in the theorem gives $4 \cdot ( (2\cdot 10 - 4 - 1 - 4)/2)^2 = 121$ for $G=K_5$, which cannot be correct since $K_5$ has $125$ spanning trees. I did not look at the proof at all to see what goes wrong (or what assumptions are tacitly made). $\endgroup$ Feb 22 at 1:51
  • $\begingroup$ There should be something that's wrong in the derivation. $\endgroup$ Feb 22 at 1:56
  • 1
    $\begingroup$ This is from Li, Jianxi, Wai Chee Shiu, and An Chang. ”The number of spanning trees of a graph.” Applied Mathematics Letters 23.3 (2010): 286-290. $\endgroup$ Feb 22 at 2:25
  • $\begingroup$ There is something that's gone wrong in the derivation. Maybe from the arithmetic mean-geometric mean inequality step itself. But I am not able to figure out where. The authors seem to be quite reputed therefore I cannot reach a conclusion. $\endgroup$ Feb 22 at 2:37
  • $\begingroup$ Update: the formula failed for complete graphs for all the tested n values. But all other mentioned graphs succeeded with the different values of n. Therefore the formula is partially correct and might need adjustments. $\endgroup$ Feb 22 at 3:23

1 Answer 1


The problem is that for a complete graph, $\mu_{n-1} \leq \delta$ is wrong, and thus $f(\delta) < f(\mu_{n+1})$. This can be fixed by adding a special case for the complete graph (for other graphs $\mu_{n-1}\leq\delta$ because the algebraic connectivity is at most the vertex connectivity).

  • $\begingroup$ What kind of special cases could be considered here? $\endgroup$ Feb 23 at 2:24
  • 2
    $\begingroup$ @NoxiousReptile: Command Master is saying the only graphs for which the theorem as stated is false are the complete graphs. $\endgroup$ Feb 23 at 3:21

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.