The Least Adjacency Eigenvalue And Odd Cycles

The Spectral Question

For a real symmetric matrix, all eigenvalues are real. An adjacency matrix is real and symmetric, so its eigenvalues can be ordered from least to greatest. This tutorial studies when the least adjacency eigenvalue is as small as it can possibly be relative to the largest one. For a connected graph, the endpoint \(-\rho\) is attained exactly when the graph is bipartite; equivalently, exactly when it has no odd cycle.

Throughout, graphs are finite and simple. For \(G=(V,E)\), the adjacency matrix \(\mathbf A(G)\) has entry \(1\) in positions \(u,v\) and \(v,u\) when \(uv\in E\), and entry \(0\) otherwise. Write \(\rho\) for the largest eigenvalue of \(\mathbf A(G)\). A graph is bipartite if its vertices can be partitioned into sets \(X,Y\) so that every edge has one endpoint in each set. Either set may be empty.

The one-vertex case is included deliberately: its adjacency matrix is \([0]\), so \(\rho=0\), and \(-\rho=0\) is an eigenvalue. That graph is bipartite. For all other connected graphs, the proof will use the fact that a largest-eigenvalue eigenvector can be chosen strictly positive.

Bounding the Adjacency Eigenvalues

For a real vector \(x=(x_v)_{v\in V}\), let \(\|x\|^2=\sum_{v\in V}x_v^2\), and let \(|x|\) denote the vector with coordinates \(|x_v|\). By the definition of adjacency,

The factor \(2\) occurs because each undirected edge contributes once in each of the two symmetric matrix positions. Since \(x_ux_v\leq |x_u||x_v|\), this identity gives \(\left|x^{\mathsf T}\mathbf A(G)x\right|\leq |x|^{\mathsf T}\mathbf A(G)|x|\).

Proof. The spectral theorem for real symmetric matrices gives an orthonormal basis of eigenvectors of \(\mathbf A(G)\). In this basis, the quotient \(y^{\mathsf T}\mathbf A(G)y/\|y\|^2\), for nonzero \(y\), is a weighted average of the eigenvalues, with nonnegative weights summing to \(1\). Its maximum is therefore the largest eigenvalue \(\rho\). Apply this maximum property to \(y=|x|\); since \(\||x|\|=\|x\|\), we obtain \[ \left|x^{\mathsf T}\mathbf A(G)x\right| \leq |x|^{\mathsf T}\mathbf A(G)|x| \leq \rho\|x\|^2. \] If \(x\) is a nonzero eigenvector with eigenvalue \(\lambda\), then \(x^{\mathsf T}\mathbf A(G)x=\lambda\|x\|^2\). Dividing the displayed bound by \(\|x\|^2>0\) proves \(|\lambda|\leq\rho\), or \(-\rho\leq\lambda\leq\rho\). \(\square\)

For a connected graph with at least two vertices, there is also a strictly positive eigenvector for \(\rho\). To see this, choose a unit vector maximizing the Rayleigh quotient, which exists because the unit sphere is compact. Replacing its coordinates by their absolute values cannot decrease the quotient, so a nonnegative maximizing vector \(y\) can be chosen. The spectral theorem’s maximum property implies \(\mathbf A(G)y=\rho y\). Also, \(\rho>0\): if \(uv\) is an edge, the vector with coordinates \(1\) at \(u,v\) and \(0\) elsewhere has quotient \(1\).

Now suppose \(y_w=0\) for some vertex \(w\). The eigenvector equation at \(w\) says \(\rho y_w=\sum_{z\in N(w)}y_z\). Its left side is zero; the right side is a sum of nonnegative terms, so every neighbor of \(w\) also has coordinate zero. Repeating this argument along paths in the connected graph would make every coordinate zero, contradicting that \(y\) is a unit vector. Thus \(y_v>0\) for every vertex \(v\).

Why the Endpoint Detects Bipartiteness

For the one direction of the theorem, bipartiteness makes the spectrum symmetric about zero. The diagonal matrix that records the two parts changes the sign of the adjacency matrix when applied on both sides.

Proof. First consider a connected graph with at least two vertices and a bipartition \(X,Y\). Define a diagonal matrix \(S\) by \(S_{vv}=1\) for \(v\in X\) and \(S_{vv}=-1\) for \(v\in Y\). Every edge crosses the partition, so for each edge \(uv\), \(S_{uu}S_{vv}=-1\). Nonedges remain nonedges, hence \(S\mathbf A(G)S=-\mathbf A(G)\). If \(y\) is the strictly positive eigenvector for \(\rho\) established above, then \[ \mathbf A(G)(Sy)=-S\mathbf A(G)y=-\rho Sy. \] Since \(Sy\neq 0\), \(-\rho\) is an eigenvalue. In the one-vertex case, the only eigenvalue is \(0=-\rho\), so the conclusion holds there too. \(\square\)

Conversely, suppose \(-\rho\) is an eigenvalue, and let \(x\neq 0\) satisfy \(\mathbf A(G)x=-\rho x\). The inequalities used to bound the eigenvalues now have equal endpoints:

Equality forces two things. First, \(|x|\) attains the maximum Rayleigh quotient, so it is an eigenvector for \(\rho\). The positivity argument above shows that \(|x_v|>0\) at every vertex. Second, equality in the first inequality requires \(x_ux_v=-|x_u||x_v|\) on every edge \(uv\). Indeed, each edge contributes a nonnegative difference \(|x_u||x_v|+x_ux_v\); their sum is zero only if every such difference is zero. Thus adjacent vertices have opposite signs. The positive and negative coordinates of \(x\) form a bipartition of \(G\). This proves the reverse direction for connected graphs with at least two vertices; the one-vertex case already satisfies both conditions.

Connecting the Criterion to Odd Cycles

A cycle is a closed path whose vertices, except for the repeated starting vertex at the end, are distinct. Its length is its number of edges. A bipartite graph cannot have an odd cycle: while following a cycle, each edge switches parts, so returning to the starting vertex requires an even number of switches. For the converse, we use the following elementary fact.

Proof. Use induction on the odd length \(\ell\) of the closed walk \(v_0,v_1,\ldots,v_\ell\), where \(v_\ell=v_0\). The length cannot be \(1\), because a simple graph has no loop. If \(v_0,\ldots,v_{\ell-1}\) are distinct, the walk is itself an odd cycle. Otherwise choose \(0\leq i<j\leq\ell-1\) with \(v_i=v_j\). The segment from \(v_i\) to \(v_j\) is a closed walk of length \(j-i\); the rest of the original walk is a closed walk of length \(\ell-(j-i)\). Both lengths are positive and smaller than \(\ell\), and their sum is odd, so one is odd. The induction hypothesis applied to that shorter odd closed walk supplies an odd cycle in the original walk. \(\square\)

Proof. The alternating-parts argument above proves that a bipartite graph has no odd cycle. Now suppose a connected graph has no odd cycle, and fix a root vertex \(r\). Partition its vertices according to whether their distance from \(r\) is even or odd. Every vertex has a finite distance because the graph is connected. If an edge \(uv\) joined two vertices whose distances had the same parity, shortest paths from \(r\) to \(u\) and from \(r\) to \(v\), together with \(uv\), would form a closed walk of length \(d(r,u)+1+d(r,v)\), which is odd. By the lemma this walk contains an odd cycle, a contradiction. Thus every edge joins opposite distance parities, giving a bipartition. \(\square\)

Combining this corollary with the spectral theorem above gives a useful equivalent description: for a connected graph, \(-\rho\) is an eigenvalue exactly when there is no odd cycle. In particular, finding one odd cycle proves that the least eigenvalue is strictly greater than \(-\rho\). The condition is about the entire connected graph: an odd cycle anywhere in it prevents equality.

Common Pitfall: Assuming Every Spectrum Is Symmetric

A mistaken argument says that every adjacency spectrum is symmetric about zero, so \(-\rho\) must always be an eigenvalue. The triangle provides a direct correction. For its adjacency matrix, the tempting alternating-sign vector \(x=(1,-1,1)\) does not give an eigenvalue \(-2\): direct multiplication gives \(\mathbf A(G)x=(0,2,0)\), whereas \(-2x=(-2,2,-2)\). The actual eigenvalues are \(2,-1,-1\). Spectral symmetry about zero is guaranteed for bipartite graphs, not for all graphs; an odd cycle such as the triangle is an obstruction.

The connectedness hypothesis also matters. For a disconnected graph, its adjacency matrix separates into blocks for its connected components, and an eigenvalue \(-\rho\) for the whole graph need not certify that every component is bipartite. For example, take the disjoint union of a triangle and a single isolated vertex. The triangle has eigenvalue \(-1\), while the isolated vertex contributes eigenvalue \(0\); the largest eigenvalue of the union is \(2\), so \(-\rho=-2\) is absent. More generally, the connected-graph criterion can be applied component by component, using each component’s own largest eigenvalue.