Hello again everybody,
I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm having difficulty justifying it. Below, I'll explain everything and state my question precisely.
Let $G=(V,E)$ be a graph and let $d_v$ denote the degree of $v\in V$. Let $T$ denote the diagonal matrix whose $(v,v)^{\text{th}}$ entry is $d_v$. The Laplacian $\mathcal{L}$ of $G$ is the matrix defined by $ \mathcal{L}_{i,j} := \Bigg\{ \begin{array}{cc} 1 & \text{if } u=v \\ -1/\sqrt{d_v d_u} & \text{if } \{u,v\} \in E \\ 0 & \text{otherwise} \end{array} $ The eigenvalues $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$ of $\mathcal{L}$ are called the eigenvalues of $G$. Since it's not too hard to show that $0=\lambda_0$ for every graph, we call $\lambda_1$ the minimal eigenvalue of $G$.
Since $\mathcal{L}$ is Hermitian, its eigenvalues are all nonnegative reals and the minimal eigenvalue is determined by the Rayleigh-Ritz ratio (see, e.g. Theorem 4.2.2 of Horn & Johnson): $ \lambda_1 = \min \frac{\langle g,\mathcal{L}g \rangle}{\langle g,g\rangle} $ Here the minimum is taken over all $g : V\rightarrow \mathbb{R}$ not identically $0$, which we think of as length-#$V$ real vectors. With some algebraic manipulation that ratio becomes $ \lambda_1 = \inf \frac{\sum_{\{u,v\}\in E} (f(u)-f(v))^2}{\sum_v f(v)^2d_v} $ where $g=T^{-1/2} f$ and the infimum is taken over all functions $f$ such that $f \bot T1$ where $1$ is the all-$1$ vector.
That formula makes sense, I think. However, later (in the proof of theorem 2.2) she states that $ \lambda_1 = \frac{\sum_{v \in V_+} f(v) \sum_{\{u,v\}\in E_+} (f(v)-f(u))}{\sum_{v\in V_+} f^2(v) d_v} $ where $V_+ := \{ v : f(v) \geq 0\}$ and $E_+ := \{ \{u,v\} \in E : u \text { or } v \in V_+\}$.
I can't understand why these two formulas for $\lambda_1$ are equivalent. Chung's silence on this point may be because the equivalence is obvious. But could someone shed light on this for me?