A proof of a conjecture of Cazenave on graph eigenvalues

Let $G$ be a finite simple connected graph on $n \ge2$ vertices, with adjacency matrix $A$ and Laplacian $L = D - A$. Write $\lambda_2$ and $\mu_2$ for their second largest eigenvalues. Stars include $K_2$. Cazenave [2 Theorem 1] proved the first inequality below and conjectured the second [2 Conjecture 6(ii)].

Let $T$ be $K_{1,3}$ with one edge subdivided, and let $\gamma$ be the middle root of $x^3 - 7x^2 + 13x - 5$. Direct calculation gives

We use Laplacian subgraph monotonicity [1 Proposition 3.2.1(ii)], which does not require induced subgraphs. The following consequence of [3 Observation 3.3 and Theorem 3.4] has a short direct proof.

Proof. We show that $G$ contains $K_3$, $P_5$ or $T$. If its maximum degree is at most two, it is a path or cycle, and the claim follows from the exclusions. Otherwise choose a vertex $h$ of degree at least three. Since $G$ is not a star, connectivity gives a neighbour $a$ of $h$ with a neighbour $b \ne h$. If $b \sim h$, then $hab$ is a triangle. Otherwise two further neighbours $c,d$ of $h$ give the copy $ha,ab,hc,hd$ of $T$. Subgraph monotonicity and the displayed spectra prove the bound.

The rounded bound below follows from Cazenave’s signed-degree estimate [2 Theorem 1 and the following remark]; we additionally prove strictness when $\lambda_2 > 0$.

Proof. Set $k = \lceil t\rceil$ and let $y$ be a $t$-eigenvector of $A$. By Perron–Frobenius, $y$ has both signs. At a positive maximum and a negative minimum, the eigenvalue equation gives at least $k$ neighbours of the same sign. Retain $k$ such edges at each vertex, forming a spanning subgraph $H$ consisting of two disjoint $K_{1,k}$’s and isolated vertices.

Choose nonzero $z$ in the two-dimensional $(k+1)$-eigenspace of $L(H)$, orthogonal to a top eigenvector of $L(G)$. Then

Thus $\mu_2 \ge k+1$. If $\mu_2 = t+1$, then $t = k$ and every omitted edge has equal $z$-values at its endpoints. The support of $z$ is a nonempty union of whole stars (each star’s top Laplacian eigenvector is proportional to $(k,-1,\ldots,-1)$), so no edge leaves it. Connectivity forces full support; hence $y$ has exactly $k+1$ positive and $k+1$ negative coordinates. Put $S=\{v:y_v>0\}$ and $d_S(v)=|N(v)\cap S|$. Summing $Ay=ky$ over $S$ gives

since $d_S(v)\le k$ on $S$, all coordinates outside $S$ are negative, and connectivity supplies a crossing edge. This contradiction proves strictness. $\square$

Proof of Theorem 1. The pairs $(\lambda_2,\mu_2)$ for $K_2$, stars of order at least three, $P_4$ and $C_4$ are, respectively,

These give the stated equalities for stars and strict inequalities for $P_4,C_4$. Together with Lemma 2, they also give $\mu_2\ge2$ for every non-star. Thus the linear bound is strict for non-stars with $\lambda_2\le0$; Lemma 3 handles $\lambda_2>0$.

For the quadratic bound, consider a non-star other than $P_4,C_4$. If $\lambda_2\le1$, Lemma 2 gives $\mu_2^2>5\ge4\lambda_2+1$. Otherwise put $t=\lambda_2>1$ and $k=\lceil t\rceil\ge2$. Then

Equality requires $k=t=2$ and $\mu_2=t+1$, contrary to Lemma 3. $\square$