10
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Sam Hopkins
    Commented Feb 22 at 1:51
  • $\begingroup$ There should be something that's wrong in the derivation. $\endgroup$
    – Noxious Reptile
    Commented 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$
    – Noxious Reptile
    Commented 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$
    – Noxious Reptile
    Commented 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$
    – Noxious Reptile
    Commented Feb 22 at 3:23

1 Answer 1

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ What kind of special cases could be considered here? $\endgroup$
    – Noxious Reptile
    Commented 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$
    – Sam Hopkins
    Commented Feb 23 at 3:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .