\documentclass[10pt]{article}
\usepackage[margin=0.75in]{geometry}
\usepackage{amsmath,amssymb,amsthm,microtype}
\usepackage[hidelinks]{hyperref}
\usepackage[small,compact]{titlesec}
\emergencystretch=1em
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\title{A proof of a conjecture of Cazenave on graph eigenvalues}
\author{Alexander M. Kramer\thanks{Independent Researcher. \texttt{akramer.alex@gmail.com}. The proof and text were developed with AI assistance, including OpenAI Codex, under the author's direction. The author checked the argument and revised the text.}}
\date{November 8, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove Cazenave's conjecture $\mu_2^2\ge4\lambda_2+1$ for connected
graphs, where $\lambda_2$ and $\mu_2$ are the second largest adjacency
and Laplacian eigenvalues. We also characterize equality in this
inequality and in the linear bound $\mu_2\ge\lambda_2+1$.
\end{abstract}

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~\cite[Theorem~1]{Cazenave} proved the first inequality below
and conjectured the second~\cite[Conjecture~6(ii)]{Cazenave}.

\begin{theorem}\label{thm:main}
Every such graph satisfies
\[
\mu_2\ge\lambda_2+1
\qquad\text{and}\qquad
\mu_2^2\ge4\lambda_2+1.
\]
Equality holds exactly for stars in the first bound, and for stars
on at least three vertices in the second.
\end{theorem}

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
\[
\mu_2(T)=\gamma\in(9/4,7/3),\qquad
\mu_2(P_5)=\frac{3+\sqrt5}{2},\qquad \mu_2(K_3)=3.
\]
We use Laplacian subgraph monotonicity
\cite[Proposition~3.2.1(ii)]{BH}, which does not require induced
subgraphs. The following consequence of
\cite[Observation~3.3 and Theorem~3.4]{LGS} has a short direct proof.

\begin{lemma}\label{lem:gap}
Unless $G$ is a star, $P_4$ or $C_4$, it satisfies
$\mu_2(G)\ge\gamma>\sqrt5$.
\end{lemma}
\begin{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.
\end{proof}

The rounded bound below follows from Cazenave's signed-degree estimate
\cite[Theorem~1 and the following remark]{Cazenave}; we additionally
prove strictness when $\lambda_2>0$.
\begin{lemma}\label{lem:signed}
If $t=\lambda_2>0$, then $\mu_2\ge\lceil t\rceil+1$ and $\mu_2>t+1$.
\end{lemma}
\begin{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
\[
(\mu_2-k-1)\|z\|^2
\ge z^{\mathsf T}(L(G)-L(H))z
=\sum_{uv\in E(G)\setminus E(H)}(z_u-z_v)^2\ge0.
\]
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
\[
k\sum_{v\in S}y_v
=\sum_{v\in S}d_S(v)y_v+\sum_{v\notin S}d_S(v)y_v
<k\sum_{v\in S}y_v,
\]
since $d_S(v)\le k$ on $S$, all coordinates outside $S$ are
negative, and connectivity supplies a crossing edge.
This contradiction proves strictness.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
The pairs $(\lambda_2,\mu_2)$ for $K_2$, stars of order at least
three, $P_4$ and $C_4$ are, respectively,
\[
(-1,0),\qquad(0,1),\qquad
\left(\frac{\sqrt5-1}{2},2\right),\qquad(0,2).
\]
These give the stated equalities for stars and strict inequalities
for $P_4,C_4$.
Together with Lemma~\ref{lem:gap}, they also give $\mu_2\ge2$
for every non-star. Thus the linear bound is strict for non-stars
with $\lambda_2\le0$; Lemma~\ref{lem:signed} handles $\lambda_2>0$.

For the quadratic bound, consider a non-star other than $P_4,C_4$.
If $\lambda_2\le1$, Lemma~\ref{lem:gap} gives
$\mu_2^2>5\ge4\lambda_2+1$.
Otherwise put $t=\lambda_2>1$ and $k=\lceil t\rceil\ge2$. Then
\[
\mu_2^2\ge(k+1)^2\ge4k+1\ge4t+1.
\]
Equality requires $k=t=2$ and $\mu_2=t+1$, contrary to
Lemma~\ref{lem:signed}.
\end{proof}

\begin{corollary}
Put $\alpha=(\sqrt5-1)/2$. Among connected graphs with
$\lambda_2>\alpha$, the minimum of $\mu_2$ is $\gamma$, attained by $T$.
\end{corollary}
\begin{proof}
Stars, $P_4$ and $C_4$ have $\lambda_2\le\alpha$, so
Lemma~\ref{lem:gap} gives the lower bound. The graph $T$ attains it,
since $\lambda_2(T)=\sqrt{2-\sqrt2}>\alpha$.
The threshold is sharp: $\lambda_2(P_4)=\alpha$ and $\mu_2(P_4)=2<\gamma$.
\end{proof}

\begin{thebibliography}{9}\small\setlength{\itemsep}{0pt}
\bibitem{BH}
A.~E.~Brouwer and W.~H.~Haemers, \emph{Spectra of Graphs},
Universitext, Springer, New York, 2012.
\href{https://doi.org/10.1007/978-1-4614-1939-6}{doi:10.1007/978-1-4614-1939-6}.
\bibitem{Cazenave}
T.~Cazenave, \emph{Lemmas and Conjectures in Spectral Graph Theory},
arXiv:2611.03879v1 [math.CO], 2 November 2026.
\href{https://arxiv.org/abs/2611.03879}{doi:10.48550/arXiv.2611.03879}.
\bibitem{LGS}
J.~Li, J.-M.~Guo and W.~C.~Shiu,
On the second largest Laplacian eigenvalues of graphs,
\emph{Linear Algebra Appl.} \textbf{438} (2013), 2438--2446.
\href{https://doi.org/10.1016/j.laa.2012.10.047}{doi:10.1016/j.laa.2012.10.047}.
\end{thebibliography}
\end{document}