Algebraic Connectivity of Trees 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?
 A: 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

*

*$u_i = \frac1a$ for $i \in A$;

*$u_i = -\frac1b$ for $i \in B$;

*$u_i = 0$ for $i \in C$.

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:

The algebraic connectivity of $G$ is at most the vertex connectivity, and equality can only be achieved when $G$ has a vertex cut $C$ such that every vertex of $C$ is adjacent to every vertex outside $C$.

(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$.
