Question: In a paper I’m reading, it makes the following statement: “It is known that among all trees on $n$ vertices the algebraic connectivity is maximized for a star”. I’ve searched around and I can’t seem to find a proof of this statement.
My attempt: Theorem 2.5.6 from Combinatorial Matrix Theory states that $$\mu(G) \leq v(G) \leq e(G),$$ where $\mu(G)$ is the algebraic connectivity, $v(G)$ is the vertex connectivity, and $e(G)$ is the edge connectivity. For any tree $T$ of order $n$, it is clear that $v(T)=e(T)=1$ (there exists only one path between any two vertices and so the removal of any edge or vertex must disconnect the tree). Therefore, from Theorem 2.5.6 we have \begin{align} \mu(T)&\leq v(T) \leq e(T) \notag\\ \implies \mu(T)&\leq 1. \label{Upper Bound of Alg on Tree} \end{align}
I can show directly (from determining the eigenvalues of the Laplacian matrix for the star) that $\mu(K_{1,n-1})=1$. Hence, by the last inequality above, $K_{1,n-1}$ has the largest algebraic connectivity among all trees on $n$ vertices.
My concern: I haven’t shown that $K_{1,n-1}$ is the only tree with algebraic connectivity 1 (is that even true?). Or is my work above sufficient to show the claim?
Some general observations: the algebraic connectivity $\mu(G)$ is given by $$\min\left\{ \frac{\mathbf u^{\mathsf T}L_G\mathbf u}{\mathbf u^{\mathsf T}\mathbf u} : \mathbf u^{\mathsf T}\mathbf 1 = 0\right\}.$$ To prove an upper bound $\mu(G) \le x$, it's enough to find a vector $\mathbf u$ for which $\mathbf u^{\mathsf T}\mathbf 1 = 0$ and $\frac{\mathbf u^{\mathsf T}L_G\mathbf u}{\mathbf u^{\mathsf T}\mathbf u} \le x$. Note also that $$\mathbf u^{\mathsf T}L_G\mathbf u = \sum_{ij \in E(G)} (u_i - u_j)^2.$$
This is exactly the strategy to prove that $\mu(G)$ (the algebraic connectivity) is less than the vertex connectivity. Suppose that you have a graph $G$ such that for some vertex cut $C$, $V(G)-C$ can be split into a disjoint union $A \cup B$ such that $G$ has no edges between $A$ and $B$. Let $a=|A|, b=|B|, c=|C|$. We want to show that $\mu(G) \le c$, so we define a vector $\mathbf u$ which will have
This is carefully defined to have $\mathbf u^{\mathsf T}\mathbf 1 = 0$. It has $\mathbf u^{\mathsf T}\mathbf u = \frac1a + \frac1b$, and $$ \mathbf u^{\mathsf T}L_G\mathbf u = \sum_{ij \in E(G)} (u_i - u_j)^2 \le ac \cdot \left(\frac1a\right)^2 + bc \cdot \left(-\frac1b\right)^2 = c\left(\frac1a + \frac1b\right). $$ This is because $(u_i - u_j)^2$ can be $\frac1{a^2}$ up to $ac$ times (when looking at an edge between $A$ and $C$), $\frac1{b^2}$ up to $bc$ times (when looking at an edge between $B$ and $C$), and is $0$ in all other cases (there are no edges between $A$ and $B$, and for edges within $A$, $B$, or $C$ the difference is $0$).
Dividing, we get $\frac{\mathbf u^{\mathsf T}L_G\mathbf u}{\mathbf u^{\mathsf T}\mathbf u} = c$, which was what we wanted.
In essentially all cases, whenever you use a theorem to prove $\le$, but you actually want to know that $=$ only holds in one case, you stare at the proof of that theorem to see where $\le$ came from.
In our case, $\le$ comes from the upper bound $ac \cdot \left(\frac1a\right)^2 + bc \cdot \left(-\frac1b\right)^2$, which assumes that all $ac$ edges between $A$ and $C$ and all $bc$ edges between $B$ and $C$ are present. We'd get a strict inequality if any of those edges were missing. So we can state a slightly more powerful theorem:
(We don't promise that equality is achieved in all such cases, only that it cannot be achieved otherwise.)
In particular, for graphs with vertex connectivity $1$, equality can only be achieved when $G$ has a cut vertex $v$ adjacent to every other vertex. If $G$ is a tree, then it must be a star centered at $v$. For all other trees, the algebraic connectivity is strictly less than $1$.