# Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula

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.

Could someone provide some insights?

• 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). Feb 22 at 1:51
• There should be something that's wrong in the derivation. Feb 22 at 1:56
• 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. Feb 22 at 2:25
• 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. Feb 22 at 2:37
• 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. Feb 22 at 3:23

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).