Largest Eigenvalue of $k$-regular graph using Perron-Frobenius Theorem

Question

I have read through the discussion of the Perron-Frobenius Theorem in Sections 8.7 and 8.8 in Algebraic Graph Theory by Godsil & Royle. They make the claim that for a connected $k$-regular graph $X$, the largest eigenvalue of the respective adjacency matrix $A$ is $k$. It is clear to me that $k$ is an eigenvalue of $A$ with eigenvector $[1 \; 1 \; \ldots \; 1 ]^T$. What is not clear to me is how the Perron-Frobenius Theorem as stated allows us to conclude that $k$ is the largest eigenvalue. Can someone explain to me why this is the case?

Answer 1

I have realized an answer to my own question.

In a lemma (8.7.1) to the proof of the Perron-Frobenius Theorem, we are able to find the largest real eigenvalue by defining the function

$$ F(x) = \min_{i; x_i \neq 0} \dfrac{(Ax)_i}{x_i} $$ where $x$ ranges over all vectors with nonnegative entries. The proof of the theorem involves finding a vector $y$ where $F$ attains its maximum value. The value of $F(y)$ is the largest real eigenvalue. This means that we just need to show that $F$ attains its maximum at the vector consisting of all ones. To see this, let $x$ be any nonzero nonnegative vector. Let $j$ be the index where $x_j$ is the largest. Then $F(x) \leq \dfrac{(Ax)_j}{x_j} \leq \dfrac{k x_j}{x_j} = k$. Equality holds if $x$ is the vector of all ones, so $F$ attains its maximum at the vector of all ones, so $k$ is indeed the largest eigenvalue of $A$.