Largest eigenvalue of a normalized graph Laplacian

Question

I was able to show that the eigenvalues of a normalized graph Laplacian matrix for some graph $G$ are in the range $[0,2]$. However, I have no idea how to show that the graph $G$ must be bipartite if $\lambda_n = 2$.

Answer 1

If $\lambda_n$ is the largest eigenvalue of the normalized Laplacian matrix of a graph $G$, then $$\lambda_n=\sup_x\frac{\sum_{u\sim v}\big(x(u)-x(v)\big)^2}{\sum_v\big(x(v)\big)^2\deg(v)}\le2$$ since $$\big(x(u)-x(v)\big)^2\le2\bigg(\big(x(u)\big)^2+\big(x(v)\big)^2\bigg).$$ Therefore, equality holds only when $x(u)=-x(v)$ for every edge $\{u,v\}$ in $G$. Now, since $x\ne0$, $G$ has a connected component.

On the other hand, if $G$ has a connected bipartite component, then we can choose $x$ so as to make $\lambda_n=2$.