[proofplan] Throughout, $A_G \in \mathbb{R}^{n \times n}$ is the adjacency matrix of $G$, which is real symmetric, hence has $n$ real eigenvalues $\lambda_1 \geq \cdots \geq \lambda_n$ with an orthonormal eigenbasis. (i) follows from the maximum-coordinate trick: normalise an eigenvector so its largest-modulus entry is $1$, then the eigenvalue equation at that coordinate bounds $|\lambda|$ by the degree. (ii) and (iii) refine this: equality in the triangle inequality forces all neighbours to share the same value, and connectedness propagates this to the entire graph; the sign structure distinguishes $+\Delta(G)$ (regular) from $-\Delta(G)$ (regular bipartite). (iv) is a one-line Rayleigh quotient computation with the all-ones vector. [/proofplan] [step:Prove $|\lambda| \leq \Delta(G)$ via the maximum-coordinate normalisation] Let $\lambda$ be an eigenvalue of $A_G$ with eigenvector $x = (x_1, \ldots, x_n)^\top \neq 0$. Choose an index $i \in \{1, \ldots, n\}$ maximising $|x_i|$ (since $x \neq 0$, $|x_i| > 0$). Replacing $x$ by $x / x_i$ if $x_i > 0$, or $x / (-x_i)$ if $x_i < 0$, and then by its complex conjugate if necessary (not needed here since $x \in \mathbb{R}^n$), we may assume \begin{align*} x_i = 1 \quad \text{and} \quad |x_j| \leq 1 \text{ for all } j. \end{align*} The eigenvalue equation $A_G x = \lambda x$ at coordinate $i$ reads \begin{align*} \lambda = \lambda x_i = (A_G x)_i = \sum_{j=1}^n (A_G)_{ij} x_j = \sum_{j \sim i} x_j. \end{align*} Applying the triangle inequality and then $|x_j| \leq 1$: \begin{align*} |\lambda| = \left|\sum_{j \sim i} x_j \right| \leq \sum_{j \sim i} |x_j| \leq \sum_{j \sim i} 1 = \deg(i) \leq \Delta(G). \end{align*} [guided] The eigenvalue equation $A_G x = \lambda x$ holds coordinate-wise: for each $i$, \begin{align*} \lambda x_i = \sum_j (A_G)_{ij} x_j = \sum_{j \sim i} x_j. \end{align*} The strategy is to pick the "best" coordinate to extract information. At the coordinate where $|x_i|$ is maximum, dividing through gives a clean equation for $\lambda$: \begin{align*} \lambda = \frac{1}{x_i} \sum_{j \sim i} x_j. \end{align*} To keep arithmetic simple, normalise the eigenvector so $x_i = 1$. Then the RHS is just $\sum_{j \sim i} x_j$, a sum over at most $\deg(i) \leq \Delta(G)$ terms, each bounded in absolute value by $1$. The triangle inequality closes the bound: \begin{align*} |\lambda| \leq \sum_{j \sim i} |x_j| \leq \deg(i) \leq \Delta(G). \end{align*} This "maximum-coordinate trick" is the standard way to bound eigenvalues of combinatorial matrices, and the equality cases drive (ii) and (iii) below. [/guided] [/step] [step:Show that $\Delta(G)$ is an eigenvalue iff $G$ is regular, with eigenvector $\mathbf{1}$ and multiplicity $1$] $(\Leftarrow)$ Suppose $G$ is $k$-regular with $k = \Delta(G)$. For each $i$, \begin{align*} (A_G \mathbf{1})_i = \sum_{j \sim i} 1 = \deg(i) = k, \end{align*} so $A_G \mathbf{1} = k \mathbf{1}$ and $\Delta(G) = k$ is an eigenvalue with eigenvector $\mathbf{1} = (1, \ldots, 1)^\top$. $(\Rightarrow)$ Suppose $\Delta(G)$ is an eigenvalue with eigenvector $x \neq 0$. Following Step 1, normalise so that there exists $i$ with $x_i = 1$ and $|x_j| \leq 1$ for all $j$. The chain of inequalities \begin{align*} \Delta(G) = |\Delta(G) \cdot x_i| = |(A_G x)_i| = \left|\sum_{j \sim i} x_j\right| \leq \sum_{j \sim i} |x_j| \leq \deg(i) \leq \Delta(G) \end{align*} must hold with equality throughout. From the last two equalities: \begin{align*} \deg(i) = \Delta(G), \qquad |x_j| = 1 \text{ for all } j \sim i. \end{align*} Equality in the triangle inequality for real numbers (with $\sum x_j = \deg(i) > 0$) forces all $x_j$ with $j \sim i$ to have the same sign and be non-negative, i.e., $x_j = 1$ for all $j \sim i$. *Propagation by connectedness.* The same argument applied at any $j \sim i$ with $x_j = 1$ yields: for all $j' \sim j$, $|x_{j'}| = 1$, $x_{j'} = 1$, and $\deg(j) = \Delta(G)$. By induction along any path in $G$ and the connectedness hypothesis, $x_v = 1$ for all $v \in V(G)$ and $\deg(v) = \Delta(G)$ for all $v$. Hence $x = \mathbf{1}$ and $G$ is $\Delta(G)$-regular. *Multiplicity.* The argument above shows that *every* eigenvector for $\Delta(G)$ equals $\mathbf{1}$ up to the normalisation (after multiplying by a scalar to achieve $x_i = 1$). Hence the eigenspace $\ker(A_G - \Delta(G) I)$ is $1$-dimensional: $\Delta(G)$ has multiplicity $1$. [guided] The forward direction $(\Leftarrow)$ is immediate: $(A_G \mathbf{1})_i$ counts the neighbours of $i$, which equals $\deg(i) = k$ under regularity. The reverse direction $(\Rightarrow)$ is where the maximum-coordinate trick is sharp. The inequality chain for $|\lambda| \leq \Delta(G)$ is saturated by assumption ($\lambda = \Delta(G)$), so *every* inequality in the chain must be an equality: 1. $|x_j| = 1$ for all $j \sim i$: otherwise, $\sum_{j \sim i} |x_j| < \deg(i)$, strict. 2. $\deg(i) = \Delta(G)$: otherwise, $\deg(i) < \Delta(G)$, strict. 3. Triangle equality: since $\sum_{j \sim i} x_j = \Delta(G) > 0$ is real positive, and each $|x_j| = 1$ with $x_j \in \mathbb{R}$, forcing $x_j = 1$ for each $j \sim i$. So at every neighbour of $i$, the eigenvector value is also $1$ and the degree equals $\Delta(G)$. But then the same argument applies at each such neighbour (they are also maximum-coordinate vertices, with $x = 1$). By induction along edges and connectedness of $G$, this propagates to *every* vertex: $x_v = 1$ and $\deg(v) = \Delta(G)$ for all $v$. So $x = \mathbf{1}$ (up to scalar) and $G$ is $\Delta(G)$-regular. Since any eigenvector for $\Delta(G)$ must be proportional to $\mathbf{1}$, the eigenspace is $1$-dimensional, giving multiplicity $1$. Where does connectedness matter? Without it, each component could have its own eigenvector, so the eigenvalue $\Delta(G)$ might have multiplicity equal to the number of components. [/guided] [/step] [step:Show that $-\Delta(G)$ is an eigenvalue iff $G$ is regular bipartite] $(\Leftarrow)$ Suppose $G$ is $k$-regular and bipartite with bipartition $V(G) = X \sqcup Y$ and $k = \Delta(G)$. Define \begin{align*} y: V(G) &\to \{+1, -1\} \\ v &\mapsto \begin{cases} +1 & v \in X, \\ -1 & v \in Y. \end{cases} \end{align*} For $v \in X$, every neighbour lies in $Y$ (bipartite), so $y_u = -1$ for all $u \sim v$, and \begin{align*} (A_G y)_v = \sum_{u \sim v} y_u = \sum_{u \sim v} (-1) = -\deg(v) = -k = -k \cdot 1 = -k y_v. \end{align*} Symmetrically for $v \in Y$: $(A_G y)_v = \sum_{u \sim v} (+1) = k = -k \cdot (-1) = -k y_v$. Hence $A_G y = -k y$, and $-k = -\Delta(G)$ is an eigenvalue with eigenvector $y$. $(\Rightarrow)$ Suppose $-\Delta(G)$ is an eigenvalue with eigenvector $x \neq 0$, normalised (as in Step 1) so that there exists $i$ with $x_i = 1$ and $|x_j| \leq 1$ for all $j$. Then \begin{align*} \Delta(G) = |(-\Delta(G)) x_i| = |(A_G x)_i| = \left|\sum_{j \sim i} x_j\right| \leq \sum_{j \sim i} |x_j| \leq \deg(i) \leq \Delta(G). \end{align*} Equality throughout forces $\deg(i) = \Delta(G)$ and $|x_j| = 1$ for $j \sim i$. Additionally, since $\sum_{j \sim i} x_j = -\Delta(G) = -\deg(i)$, triangle equality for reals forces $x_j = -1$ for all $j \sim i$. *Propagation.* Applying the same argument at any $j \sim i$ with $x_j = -1$: at coordinate $j$, the eigenvector equation gives $\sum_{k \sim j} x_k = -\Delta(G) \cdot x_j = -\Delta(G) \cdot (-1) = \Delta(G)$. By an analogous equality analysis, $\deg(j) = \Delta(G)$ and $x_k = +1$ for all $k \sim j$. Iterating by connectedness: every vertex $v$ has $x_v \in \{+1, -1\}$, every vertex has degree $\Delta(G)$ (so $G$ is regular), and every edge $uv$ satisfies $x_u x_v = -1$, i.e., adjacent vertices have opposite sign. Setting $X := \{v : x_v = +1\}$ and $Y := \{v : x_v = -1\}$ gives a bipartition, so $G$ is bipartite. [guided] The structure mirrors Step 2 but with a sign flip. $(\Leftarrow)$: A bipartite regular graph naturally carries a $\pm 1$-valued function $y$ that flips sign across each edge. Since all neighbours of a $+1$-vertex are $-1$-vertices (and vice versa), summing over neighbours gives $-k$ times the original sign — which is exactly the eigenvalue equation for $-k$. $(\Rightarrow)$: Apply the maximum-coordinate trick at the eigenvalue $-\Delta(G)$. Equality in $|{-}\Delta(G)| \leq \Delta(G)$ saturates the chain of inequalities, forcing all neighbours of the max-coordinate vertex to have $|x_j| = 1$. The sign is determined by the *sign* of $\sum x_j$: we need $\sum_{j \sim i} x_j = -\Delta(G) = -\deg(i)$. With each $|x_j| = 1$, this forces each $x_j = -1$. Propagating: the neighbours of those neighbours must have $x = +1$, and so on, alternating across edges. Connectedness fills in every vertex with a sign $\in \{\pm 1\}$, with adjacent vertices of opposite signs — precisely a bipartition. Regularity comes along for free from each $\deg$ equality. Why does the connectedness matter here? If $G$ were disconnected, each component could independently have eigenvalue $-\Delta(G)$, and the global eigenvector would be a $\pm 1$ function on components, not necessarily a bipartition of the whole graph. [/guided] [/step] [step:Bound $\lambda_1 \geq \delta(G)$ via the Rayleigh quotient with $\mathbf{1}$] Since $A_G$ is real symmetric, the [Courant–Fischer min-max principle](/theorems/???) gives \begin{align*} \lambda_1 = \max_{v \in \mathbb{R}^n \setminus \{0\}} \frac{\langle v, A_G v \rangle}{\langle v, v \rangle}. \end{align*} Apply this with $v = \mathbf{1}$, noting $\langle \mathbf{1}, \mathbf{1}\rangle = n$ and \begin{align*} \langle \mathbf{1}, A_G \mathbf{1} \rangle = \sum_{i, j} (A_G)_{ij} = 2|E(G)| = \sum_{i=1}^n \deg(i), \end{align*} by the [handshake lemma](/theorems/???). Therefore \begin{align*} \lambda_1 \geq \frac{\langle \mathbf{1}, A_G \mathbf{1} \rangle}{\langle \mathbf{1}, \mathbf{1} \rangle} = \frac{1}{n} \sum_{i=1}^n \deg(i) = \bar{d}(G), \end{align*} the average degree of $G$. Since $\bar{d}(G) \geq \delta(G)$ (an average is at least the minimum), we conclude \begin{align*} \lambda_1 \geq \delta(G). \end{align*} [/step] [step:Combine the four parts] Parts (i)–(iv) have been proved in Steps 1–4 respectively. Together they constitute the theorem, using real symmetry of $A_G$ throughout (which guarantees a real eigenbasis and justifies the Rayleigh-quotient characterisation of $\lambda_1$). [/step]