\documentclass[11pt]{article}
\usepackage[a4paper,margin=25mm]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,booktabs,array}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{microtype,indentfirst,xcolor}
\urlstyle{same}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\turan}{t_2}
\newcommand{\circum}{\operatorname{circ}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\title{Hilton's conjecture on cycle multiplicities}
\author{Qiyue Tang}
\date{2 November 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove Hilton's conjecture on the number of cycles of each length in dense Hamiltonian graphs. This resolves the problem posed by A.\,J.\,W. Hilton and recorded by Sheehan in 1977.
\end{abstract}
\begingroup
\renewcommand\thefootnote{}\footnotetext{\textit{2020 Mathematics Subject Classification.} Primary 05C38; Secondary 05C35, 05C45.\newline
\textit{Keywords.} Hilton's conjecture, Hamiltonian graph, cycle multiplicity, weak pancyclicity.}
\endgroup

\begingroup\color{blue}
\section*{AI use and scholarly credit}
The research reported here was developed in a ChatGPT-6-Pro conversation in approximately 56 minutes; the recorded session, including organization and delivery checks, lasted approximately 74 minutes. Codex was used for adversarial review and expository revision. The proof has passed an external Rethlas-OSV review \cite{OSV,RethlasOSV}.

By posting this manuscript on this platform, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in preparing a finished account or checking the arguments; the eventual scholarly credit should go to those who undertake that work.
\par\endgroup

\section{Introduction}
Degree and edge conditions that force a Hamilton cycle often also force shorter cycles. Dirac's theorem \cite{Dirac} states that a graph on $n\ge3$ vertices with minimum degree at least $n/2$ has a cycle through all its vertices. Bondy \cite{Bondy} strengthened this conclusion in 1971: such a graph contains a cycle of every length from $3$ to $n$, unless it is a balanced complete bipartite graph. A graph containing all these lengths is called pancyclic. The bipartite exception shows why the existence of a Hamilton cycle and the existence of odd cycles must be distinguished.

Throughout this paper, graphs are finite and simple. For a graph $G$, write $V(G)$ and $E(G)$ for its vertex and edge sets, $n=|V(G)|$ for its order, and $e(G)=|E(G)|$ for its size. A graph is Hamiltonian if it has a Hamilton cycle, that is, a simple cycle through all its vertices. For an integer $\ell\ge3$, let $c_\ell(G)$ denote the number of simple cycles of length $\ell$, counted without an orientation or a distinguished initial vertex. Additional chords are allowed in the counted cycles. The symbols $\floor{x}$ and $\ceil{x}$ denote the greatest integer at most $x$ and the least integer at least $x$.

Sheehan's 1977 paper \cite{Sheehan} studies how dense a graph with exactly one Hamilton cycle can be. He proves that the largest possible number of edges is $\floor{n^2/4}+1$ for $n\ge4$. Consequently, exceeding this threshold forces a second Hamilton cycle. The same paper gives the stronger conclusion that a Hamiltonian graph $G$ satisfying
\begin{equation}\label{eq:hiltondensity}
e(G)>\floor{n^2/4}+1
\end{equation}
has at least two cycles of each length $3\le\ell\le n$. It also records Hilton's conjecture that
\begin{equation}\label{eq:hiltonbound}
c_\ell(G)\ge n-\ell+2\qquad(3\le\ell\le n).
\end{equation}
For $\ell=n$, this is the two-Hamilton-cycle conclusion. For shorter lengths it asks for a lower bound increasing with $n-\ell$, so pancyclicity alone is insufficient.

The triangle endpoint is consistent with the classical triangle-counting theorem of Erd\H{o}s \cite{ErdosTriangles}. Its bound $c_3(G)\ge n-1$ is sharp for infinitely many orders. To see the sharpness, let $n=2m+1$ with $m\ge2$, start with the complete bipartite graph with parts of sizes $m$ and $m+1$, and add two distinct edges within the larger part. The resulting graph is Hamiltonian: use one added edge to join two vertices of the larger part and alternate through the remaining vertices of the two parts. Its size is $m(m+1)+2$, and each triangle uses one added edge and one vertex of the smaller part. Hence it has exactly $2m=n-1$ triangles.

Existence theorems below the threshold in \eqref{eq:hiltondensity} provide tools for the counting problem. Brandt \cite{Brandt} proved that a nonbipartite graph of order $q$ and more than $(q-1)^2/4+1$ edges contains every cycle length from $3$ to its circumference. Brandt, Faudree and Goddard \cite{BFG} obtained a corresponding conclusion under the minimum-degree condition $(q+2)/3$, allowing girth $3$ or $4$. Here the circumference is the longest cycle length and the girth is the shortest; a graph containing every length between them is called weakly pancyclic. These results supply intermediate lengths once a sufficiently long cycle is available. In the Hamiltonian setting, He and Hu \cite{HeHu} proved weak pancyclicity for nonbipartite graphs with at least $\floor{n^2/4}-n+12$ edges.

Li, Xu and Zhou \cite{LXX} proved \eqref{eq:hiltonbound} for all $n\ge440$. Their Theorem 3.1 treats every order for $\ell=3,4,5$ and $\ell\ge11$, as well as all but the following ranges for the five remaining lengths:
\[
\begin{array}{c|ccccc}
\ell&6&7&8&9&10\\\hline
\text{remaining orders }n&11\text{--}38&13\text{--}359&15\text{--}96&17\text{--}439&19\text{--}123.
\end{array}
\]
Their proof converts a failure of the counting bound into a dense spanning Hamiltonian graph without a cycle of the chosen length. A further argument excludes the bipartite case. This connects cycle multiplicity with extremal bounds for a single forbidden length. We complete the five short-length cases and obtain Hilton's conjecture in full.

\begin{theorem}\label{thm:hilton}
Every Hamiltonian graph $G$ of order $n$ with $e(G)>\floor{n^2/4}+1$ satisfies
\[
c_\ell(G)\ge n-\ell+2\qquad(3\le\ell\le n).
\]
\end{theorem}

The proof uses the counterexample reduction of Li--Xu--Zhou \cite[Lemma 3.3]{LXX}. For an uncovered length, a counterexample would give a spanning Hamiltonian nonbipartite graph with no cycle of that length and with at least $\floor{n^2/4}-n+\ell+1$ edges. We exclude such graphs by the following stronger existence statement.

A graph is 2-connected if it has at least three vertices and remains connected after deletion of any one vertex. Write $C_\ell$ for a simple cycle of length $\ell$ and $t_2(n)=\floor{n^2/4}$ for integers $n\ge0$.
\begin{theorem}\label{thm:main}
Let $\ell\in\{6,7,8,9,10\}$ and $n\ge2\ell-1$.
If $H$ is a 2-connected nonbipartite graph of order $n$ and
\begin{equation}\label{eq:density}
e(H)\ge\turan(n)-n+\ell+1,
\end{equation}
then $H$ contains $C_\ell$.
For even $\ell$, the nonbipartiteness assumption may be omitted.
\end{theorem}

We remove at most three vertices of low degree. A bipartite remainder supplies paths of prescribed lengths, which close through an ear when an odd cycle is needed. For a nonbipartite remainder, classical weak-pancyclicity results reduce the problem to bounding the circumference. Edge bounds settle $n\ge2\ell+1$; at the two boundary orders, a block calculation determines the remainder closely enough to close a cycle using 2-connectivity.

\section{Preliminaries}
A path and a cycle have distinct vertices, apart from the repeated initial vertex used to close a cycle. Their lengths are their numbers of edges. The internal vertices of a path are all vertices other than its two endpoints. For a vertex $v$ of a graph $J$, $N_J(v)$ is its neighbor set, its degree is $|N_J(v)|$, and $\delta(J)$ is the minimum degree. We omit the subscript on $N$ when the graph is fixed. For a vertex set $S$, $J-S$ is the induced subgraph on $V(J)\setminus S$. A graph is bipartite if its vertices can be partitioned into two sets so that every edge joins the two sets. The complete graph on $a$ vertices is $K_a$. For nonnegative integers $a,b$, $\binom ab$ is the number of $b$-element subsets of an $a$-element set, and it is zero if $b>a$. Integer intervals include both endpoints. A $C_\ell$-free graph has no subgraph isomorphic to $C_\ell$. A cut vertex is a vertex whose deletion increases the number of connected components; a bridge is an edge whose deletion increases that number.

We use the following classical results with their exact hypotheses.
\begin{enumerate}
\item A nonbipartite graph of order $q$ and minimum degree at least
$(q+2)/3$ is weakly pancyclic and has girth 3 or 4
\cite[Theorem 1.7]{BFG}. 
\item A nonbipartite graph of order $q$ with more than
$(q-1)^2/4+1$ edges contains every cycle length between 3 and its
circumference \cite{Brandt}; see also \cite[Theorem 2.12]{BFG}.
\item A graph of order $q$ and circumference at most $c$ has at most
$c(q-1)/2$ edges \cite[Theorem 2.7]{EG}.
\item If $J$ is 2-connected, $b=|V(J)|\ge k\ge5$, and
$\circum(J)<k$, then
\begin{equation}\label{eq:kopylov}
 e(J)\le\max\{h(b,k,2),h(b,k,\floor{(k-1)/2})\},\qquad
 h(b,k,a)=\binom{k-a}{2}+a(b-k+a).
\end{equation}
Here $h(b,k,a)$ is defined for integers $b\ge k\ge5$ and $2\le a\le\floor{(k-1)/2}$. This is Kopylov's bound \cite{Kopylov}; an accessible precise statement
and a subsequent proof are given in \cite[Theorem 1.3]{FKLV} and
\cite[Theorems 1.3--1.4]{Luo}.
\end{enumerate}

\section{Paths and parity}
\begin{lemma}\label{lem:bippaths}
Let $R$ have bipartition $(A,B)$, and let $k\ge3$. Suppose that
$|B|\ge k$, every vertex has degree at least 2, every pair of distinct
vertices in $B$ has at least $k$ common neighbors in $A$, and every pair
of distinct vertices in $A$ has a common neighbor in $B$.
Then $R$ is connected, contains $C_{2k}$, and, between every pair of
distinct prescribed vertices, contains a path of each length
$t\in[2,2k-1]$ compatible with the bipartition: $t$ is even for endpoints in the same part and odd for endpoints in different parts.
\end{lemma}
\begin{proof}
All vertices of $B$ lie in the same component because each pair has a
common neighbor; every vertex of $A$ has a neighbor, so $R$ is connected.
Choose $k$ distinct vertices of $B$ in cyclic order, and successively
choose distinct common neighbors in $A$ for the $k$ consecutive pairs.
At the $i$th choice, only the $i-1\le k-1$ previously chosen vertices of $A$ are forbidden. The resulting alternating closed sequence uses distinct vertices in each part and gives $C_{2k}$.

For endpoints in $B$ and length $2j$, choose $j-1$ further distinct
vertices in $B$ and fill the $j$ intervening positions by distinct common
neighbors in $A$. Here $1\le j\le k-1$, so the $j+1$ required vertices of $B$ exist; at any common-neighbor choice fewer than $k$ vertices of $A$ are forbidden.
For endpoints $x,y\in A$, length 2 is supplied by the hypothesis. For
length $2j\ge4$, choose distinct vertices $b_1\in N(x)$ and
$b_j\in N(y)$, then $j-2$ further distinct vertices in $B$. This is
possible since both endpoint degrees are at least 2 and $j\le k-1$.
For consecutive $B$ pairs choose $j-1$ distinct common neighbors avoiding
$x,y$. Before the last choice at most $j$ candidates are forbidden,
and $j\le k-1$.
Finally, for $x\in A$, $y\in B$, and length $2j+1$, choose
$b_1\in N(x)\setminus\{y\}$ and then $j-1$ further distinct $B$
vertices, excluding $y$. Fill the $j$ gaps in the sequence
$b_1,\ldots,b_j,y$ with distinct common neighbors avoiding $x$.
Again at most $j\le k-1$ candidates are forbidden at a choice.
All resulting paths are simple.
\end{proof}

\begin{lemma}\label{lem:ear}
Let $H$ be 2-connected and nonbipartite, let $S\subseteq V(H)$, and let $R=H-S$ be a connected
induced bipartite graph with at least two vertices. Fix a coloring $\chi:V(R)\to\{0,1\}$ that is constant on each part and has different values on the two parts. There is a simple path $P$ with distinct endpoints
$u,v\in R$, all internal vertices in $S$, and
\[
 |E(P)|\not\equiv\chi(u)+\chi(v)\pmod2.
\]
In particular, $2\le |E(P)|\le|S|+1$.
\end{lemma}
\begin{proof}
Take an odd cycle $D$ in $H$. If $D$ meets $R$ in at least two vertices,
partition $D$ into the segments between consecutive visits to $R$.
Each visited vertex of $R$ contributes its color twice to the sum of endpoint colors. That sum is therefore even modulo $2$, whereas the sum of the segment lengths is odd. At least one segment has the required parity.

If $D$ avoids $R$, the set version of Menger's theorem gives two
vertex-disjoint $D$--$R$ paths with distinct endpoints on both sets.
Indeed, a separating set of size at most one would contradict
2-connectivity, since both sets retain a vertex after its deletion.
Truncate the paths so their interiors avoid $D\cup R$. The two arcs
of $D$ between their endpoints have opposite parity. The total length of the two connecting paths is fixed. Adding the two different arcs therefore gives opposite parities for two simple paths with the same endpoints in $R$. Choose the parity different from the sum of their endpoint colors; all other vertices lie outside $R$.

If $D\cap R=\{v\}$, use connectivity of $H-v$ to choose a shortest
$(D-v)$--$(R-v)$ path. Its interior avoids both sets. If its endpoints are $x\in D-v$ and $y\in R-v$, the two $v$--$x$ arcs of $D$ have opposite parities. Choose the arc whose length, added to the length of the connecting path, differs from $\chi(v)+\chi(y)$ modulo $2$.
In all cases the path is simple and its interior lies in $S$.
Length 1 is impossible, since $R$ is induced and bipartite.
\end{proof}

\begin{lemma}\label{lem:nearclique}
In $K_a$ with at most two edges deleted, where $a\ge5$, every two
distinct prescribed vertices are joined by a simple path of every
length $L$ with $2\le L\le a-3$.
\end{lemma}
\begin{proof}
Let the prescribed endpoints be $x,y$. Greedily build a path of length
$L-2$ starting at $x$ and avoiding $y$. If $i<L-2$ edges of the prefix have been chosen, the number of vertices outside that prefix and distinct from $y$ is $a-i-2\ge a-L+1\ge4$. Thus at every required extension there are at least four candidates, and the current
vertex has at most two nonneighbors. Let $z$ be the last vertex of this
prefix; for $L=2$ the prefix is the single vertex $x=z$.
There are $a-L\ge3$ vertices outside the prefix and outside $\{y\}$.
At most two fail to be adjacent to both $z$ and $y$, because each failing candidate accounts for a missing edge incident with $z$ or $y$, and the entire graph has at most two missing edges. Choose a common neighbor
among the others and append the two-edge path to $y$.
\end{proof}

\section{Short cycles in dense 2-connected graphs}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Suppose, for a contradiction, that $H$ satisfies Theorem~\ref{thm:main}
and has no $C_\ell$.

\textit{Pruning.} At each step delete a vertex of degree strictly less
than $(q+2)/3$, where $q$ is the current order. Stop when no such vertex
exists, or after three deletions. Let $S$ be the deleted set,
$r=|S|\le3$, $R=H-S$, and $q=n-r$. Put
\[
 L_r(n)=\sum_{i=0}^{r-1}\floor{(n-i+1)/3},\qquad
 M_r(n)=\turan(n)-n+\ell+1-L_r(n).
\]
An empty sum is zero, so $L_0(n)=0$. Index the deletions by $i=0,\ldots,r-1$. At the $i$th deletion the order is $n-i$, and the largest integer strictly less than $(n-i+2)/3$ is $\floor{(n-i+1)/3}$. Also, three consecutive integers have floor quotients by $3$ summing to their middle integer minus $1$, so $L_3(n)=n-1$. Since $n=q+3$ when $r=3$, we have
\[
\floor{n^2/4}-2n+\ell+2=\floor{(n-4)^2/4}+\ell-2=\turan(q-1)+\ell-2.
\]
Consequently
\begin{equation}\label{eq:residual}
 e(R)\ge M_r(n),\qquad L_3(n)=n-1,\qquad
 M_3(n)=\turan(q-1)+\ell-2\quad(r=3).
\end{equation}
If $r<3$, then $\delta(R)\ge d:=\ceil{(q+2)/3}$.

\textit{Bipartite remainder.} Assume first that $R$ is bipartite with parts $A,B$ of sizes $a\le b$.
Set $k=\floor{\ell/2}$, so $3\le k\le5$.
For $r<3$ we have $a,b\ge d$, and each pair of vertices in $B$ has at least
\begin{equation}\label{eq:codeg}
 2d-a\ge2\ceil{(q+2)/3}-\floor{q/2}
\end{equation}
common neighbors. Since $q\ge2\ell-3$,
\[
2\ceil{(q+2)/3}-\floor{q/2}
\ge \frac{2(q+2)}3-\frac q2
=\frac{q+8}{6}\ge\frac{2\ell+5}{6}.
\]
The left-hand side is an integer, so it is at least
$\ceil{(2\ell+5)/6}$. For $\ell=6,7,8,9,10$, these values are
$3,4,4,4,5$, respectively, and are at least $k=\floor{\ell/2}$. Each pair in $A$ has
at least $2d-b\ge3d-q\ge2$ common neighbors. Also $|B|\ge d\ge k$.
Thus Lemma~\ref{lem:bippaths} applies.

For $r=3$, put $t=ab-e(R)$, the total number of missing cross edges.
Since $a+(b-1)=q-1$, equation~\eqref{eq:residual} gives
\begin{equation}\label{eq:missing}
 a-t=e(R)-a(b-1)\ge e(R)-\turan(q-1)\ge\ell-2.
\end{equation}
Every vertex has degree at least $a-t$, and every pair in either part
has at least $a-t$ common neighbors in the other part: for a pair in $B$, its missing-neighbor union in $A$ has size at most $t$, and for a pair in $A$ the corresponding common-neighbor bound is $b-t\ge a-t$. The same missing-edge budget gives the degree bound.
Both parts have at least $\ell-2\ge k$ vertices. Again
Lemma~\ref{lem:bippaths} applies.

For even $\ell=2k$, that lemma directly contradicts $C_\ell$-freeness.
For odd $\ell\in\{7,9\}$, if $r=0$ the bipartiteness of $R=H$ is already
a contradiction. Otherwise apply Lemma~\ref{lem:ear}. Its ear has length
$p\in[2,r+1]\subseteq[2,4]$. The length $\ell-p$ lies in
$[2,\ell-2]=[2,2k-1]$ and is compatible with the endpoint colors.
The prescribed path of that length in $R$, together with the ear, is
a simple $C_\ell$, because their interiors are disjoint.
Consequently the bipartite branch is impossible.

\medskip\noindent\textit{Nonbipartite remainder.}
Now $R$ is nonbipartite. If $r<3$, the degree theorem listed above makes
$R$ weakly pancyclic with girth at most 4. If $r=3$, equation~\eqref{eq:residual}
gives $e(R)\ge\floor{(q-1)^2/4}+\ell-2>(q-1)^2/4+1$, so the edge theorem
does the same, with girth 3. Since $\ell\ge6$ and $R$ is $C_\ell$-free,
\begin{equation}\label{eq:circ}
 \circum(R)\le c:=\ell-1,\qquad e(R)\le c(q-1)/2.
\end{equation}

Define the doubled gap
\[
 D_r(n)=2M_r(n)-c(n-r-1).
\]
For $n\ge2\ell+1$ and $0\le r\le2$,
\[
 D_r(n)-D_{r+1}(n)=2\floor{(n-r+1)/3}-c
 \ge2\floor{2\ell/3}-(\ell-1)\ge(\ell-3)/3>0.
\]
The final inequality uses $\floor{x}\ge x-1$. Thus $D_r(n)\ge D_3(n)$. Equation~\eqref{eq:residual} gives
\[
 D_3(n)=2\turan(n-4)+2\ell-4-(\ell-1)(n-4).
\]
At $n=2\ell+1$ this is $\ell-3>0$. Its increment when $n$ increases by
one is $2\floor{(n-3)/2}-(\ell-1)\ge\ell-1>0$.
This contradicts~\eqref{eq:circ} for every $n\ge2\ell+1$.
At $n=2\ell$, the same comparison gives $D_0(2\ell),D_1(2\ell)\ge D_2(2\ell)$, and
\[
 D_2(2\ell)=3\ell-1-2\floor{(2\ell+1)/3}-2\floor{2\ell/3}
 \ge(\ell-5)/3>0.
\]
The displayed lower bound follows from replacing each floor by its argument. For $D_0(2\ell)-D_1(2\ell)$ and $D_1(2\ell)-D_2(2\ell)$, the smallest relevant floor is $\floor{2\ell/3}$, so the same comparison applies. At $n=2\ell-1$, $r=0$ gives $D_0(2\ell-1)=2$.
Only the following cases remain:
\begin{equation}\label{eq:boundary}
 n=2\ell-1,\ r\in\{1,2,3\};\qquad n=2\ell,\ r=3.
\end{equation}

\medskip\noindent\textit{Blocks at the boundary orders.}
Retain $c=\ell-1\in\{5,6,7,8,9\}$. A block is a maximal 2-connected
subgraph, with a bridge regarded as a block of order 2. By Kopylov's bound,
every block of a graph with circumference at most $c$ and order $b$ has
at most
\[
 B_c(b)=\begin{cases}
 \binom b2,&2\le b\le c,\\
 \max\{h(b,c+1,2),h(b,c+1,\floor{c/2})\},&b\ge c+1
 \end{cases}
\]
edges. If $R$ is disconnected, join its components by bridges to obtain
$R^+$. This adds no cycles. Let $b_1,\ldots,b_s$ be the orders of all blocks of $R^+$. Each edge belongs to exactly one block. The identity $\sum_{i=1}^s(b_i-1)=q-1$ follows by successively deleting a block that meets the other blocks at a single cut vertex: deleting its other $b_i-1$ vertices preserves connectedness and removes precisely that weight. This also handles bridge blocks; the induction ends with one block. Define the block weights $w_i=b_i-1$. They satisfy
\begin{equation}\label{eq:blockbudget}
 \sum_iw_i=W:=q-1,\qquad M_r(n)\le e(R)\le e(R^+)\le\sum_i B_c(w_i+1).
\end{equation}
In~\eqref{eq:boundary}, $W\in\{2c-3,2c-2,2c-1\}<2c$.

\smallskip\noindent\textit{Large blocks.}
At most one weight can satisfy $w\ge c$. The other weights sum to $W-w\le c-1$. Their total edge bound is at most $\binom{W-w+1}{2}$, since
\[
\binom{x+y+1}{2}-\binom{x+1}{2}-\binom{y+1}{2}=xy\ge0
\]
for nonnegative integers $x,y$, and the bound may be applied repeatedly.
For $w\ge c$, $B_c(w+1)$ is the maximum of two affine functions of $w$.
Thus $B_c(w+1)+\binom{W-w+1}{2}$ is convex, and its maximum for
$c\le w\le W$ is
\begin{equation}\label{eq:largecap}
 U_c(W)=\max\left\{B_c(c+1)+\binom{W-c+1}{2},\ B_c(W+1)\right\}.
\end{equation}
The two branches in $B_c(b)$, expanded directly from \eqref{eq:kopylov}, are
\[
\binom{c-1}{2}+2(b-c+1),\qquad
\binom{c+1-\floor{c/2}}{2}
+\floor{c/2}\bigl(b-c-1+\floor{c/2}\bigr).
\]
Their maximum gives the first four columns below. The final three columns use \eqref{eq:largecap}; for example,
$U_5(7)=\max\{10+\binom32,14\}=14$.
\[
\begin{array}{c|rrrr|rrr}
c&B_c(c+1)&B_c(2c-2)&B_c(2c-1)&B_c(2c)&U_c(2c-3)&U_c(2c-2)&U_c(2c-1)\\\hline
5&10&14&16&18&14&16&20\\
6&15&24&27&30&24&27&30\\
7&19&31&34&37&31&34&40\\
8&26&46&50&54&46&50&54\\
9&32&55&59&63&55&60&68
\end{array}
\]
In particular,
\begin{equation}\label{eq:uniformcaps}
\begin{split}
U_c(2c-3)&\le(c-1)^2-1,\\
U_c(2c-2)&\le c(c-1)-3,\\
U_c(2c-1)&\le c(c-1)\qquad(5\le c\le9).
\end{split}
\end{equation}

At $n=2\ell-1=2c+1$, the residual bounds simplify to
\begin{equation}\label{eq:boundaryM}
 \begin{split}
 M_1(n)&=c(c-1)+1+\ceil{(c-2)/3},\\
 M_2(n)&=c(c-1)-\bigl(\ceil{c/3}-1\bigr),\\
 M_3(n)&=(c-1)^2.
 \end{split}
\end{equation}
At $n=2\ell=2c+2$, $M_3(2\ell)=c(c-1)$.
Since $5\le c\le9$, the deficit $\ceil{c/3}-1$ is at most 2.
At odd order, the differences between the lower bounds for $r=1,2,3$ and the corresponding caps are, respectively,
\[
1+\ceil{(c-2)/3},\qquad4-\ceil{c/3},\qquad1.
\]
They are positive for $5\le c\le9$. At even order with $r=3$, the difference is $3$. Thus every block has order at most $c$.

\smallskip\noindent\textit{Small blocks.}
Each weight is at most $c-1$ and contributes at most $\binom{w+1}{2}$ edges. If $1\le x\le y<c-1$, transferring one unit from $x$ to $y$ changes their total bound by
\[
\binom{x}{2}+\binom{y+2}{2}-\binom{x+1}{2}-\binom{y+1}{2}
=y-x+1>0.
\]
Discard a zero weight. Repeating this operation leaves at most one weight smaller than $c-1$. Thus the unique maximizing partitions for total weights $2c-3,2c-2,2c-1$ are
\[
(c-2,c-1),\qquad(c-1,c-1),\qquad(1,c-1,c-1),
\]
with edge bounds $(c-1)^2$, $c(c-1)$ and $c(c-1)+1$, respectively.

At total weight $2c-2$, any other partition loses at least $c-2$ edges. If one part is $c-1$, the best nontrivial split of the remainder is $(c-2,1)$, with loss
\[
\binom c2-\binom{c-1}{2}-1=c-2.
\]
If no part is $c-1$, apply the same concentration argument with cap $c-2$. The best partition is $(c-2,c-2,2)$; its loss is
\[
c(c-1)-2\binom{c-1}{2}-3=2c-5\ge c-2.
\]
Since $c\ge5$, the loss is at least $3$.

At $n=2\ell-1$, $r=1$, the maximum is $c(c-1)+1<M_1(n)$, by
\eqref{eq:boundaryM}; this excludes $r=1$.
At $r=2$, the maximum is $c(c-1)$ and its excess over $M_2(n)$ is
$\ceil{c/3}-1\le2$. Thus only two blocks of order $c,c$ can occur,
with at most that many missing clique edges in total.
At $r=3$, the maximum $(c-1)^2$ equals $M_3(n)$,
so the blocks are complete and have orders $c,c-1$.
At $n=2\ell$, $r=3$, the maximum $c(c-1)$ also equals $M_3(2\ell)$,
so there are two complete blocks of order $c,c$.

None of the permitted block partitions contains an order-2 block.
Consequently no connecting bridge was added in forming $R^+$, so $R$
itself is connected. The two blocks share exactly one cut vertex $v$.

\medskip\noindent\textit{Closing the cycle.}


Let the two blocks found above be $A,B$, with shared cut vertex $v$.
Since $H-v$ is connected, take a shortest path $P$ from $A-v$ to $B-v$
in $H-v$, with endpoints $a,b$. If an internal vertex were in $A-v$, its suffix would be a shorter connecting path; if it were in $B-v$, its prefix would be shorter. Since $R$ is the union of the two blocks and $v$ is excluded, its interior avoids $R$. There is no edge between the two blocks away from $v$.
Thus $2\le p:=|E(P)|\le r+1$ and all internal vertices lie in $S$.
An $a$--$v$ path in $A$ and a $v$--$b$ path in $B$, whose lengths sum to
$\ell-p$, close with $P$ into a simple $C_\ell$.

For $r=3$ both blocks are complete, of orders $(\ell-1,\ell-2)$ or
$(\ell-1,\ell-1)$. Use a length-1 path in the larger block and a path
of length $\ell-p-1$ in the other. This length lies in $[1,\ell-3]$,
so it is available even in the smaller block: in a complete graph of order $a$, a path of any length from $1$ to $a-1$ between fixed distinct endpoints is obtained by choosing and ordering the required number of other vertices.

For $r=2$, both blocks have order $\ell-1$ and at most two edges in
total are missing. If $\ell\ge7$, take lengths 2 and $\ell-p-2$;
both lie in $[2,\ell-4]$, so Lemma~\ref{lem:nearclique} applies.
If $\ell=6$, the deficit $\ceil{5/3}-1=1$ permits at most one missing
edge in total. For $p=2$ take
lengths 2 and 2; each prescribed endpoint pair in a $K_5$ missing at most one edge has a common neighbor, since among the three other vertices at most one is excluded. For $p=3$, at least one of $av,vb$ is present; use it
and a length-2 path in the other block.
Every case gives a contradiction.
\end{proof}

\section{Proof of Hilton's conjecture}
\begin{proof}[Proof of Theorem~\ref{thm:hilton}]
By Theorem 3.1 of Li--Xu--Zhou \cite{LXX}, it remains to consider $\ell\in\{6,7,8,9,10\}$ and $n\ge2\ell-1$. Suppose that $c_\ell(G)\le n-\ell+1$. To obtain the density needed for the reduction, fix a Hamilton cycle $C$ of $G$. Every $\ell$-cycle has an edge outside $C$, because $\ell<n$. Choose one such edge from every $\ell$-cycle and delete the set of chosen edges. At most $n-\ell+1$ edges are deleted; the resulting spanning graph $H$ retains $C$ and is $C_\ell$-free. Moreover,
\[
e(H)\ge e(G)-(n-\ell+1)\ge\floor{n^2/4}+2-(n-\ell+1).
\]
Lemma 3.3 of \cite{LXX}, applied to this construction, gives the additional conclusion that $H$ is nonbipartite. Therefore $H$ is a spanning Hamiltonian nonbipartite $C_\ell$-free graph with
\[
e(H)\ge\floor{n^2/4}-n+\ell+1.
\]
The graph $H$ is 2-connected because it contains a Hamilton cycle. Theorem~\ref{thm:main} therefore gives $C_\ell$ in $H$, a contradiction.
\end{proof}

\begin{thebibliography}{99}
\bibitem{Dirac} G. A. Dirac, \emph{Some theorems on abstract graphs}, Proceedings of the London Mathematical Society (3) 2 (1952), 69--81. \url{https://doi.org/10.1112/plms/s3-2.1.69}.
\bibitem{Bondy} J. A. Bondy, \emph{Pancyclic graphs I}, Journal of Combinatorial Theory, Series B 11 (1971), 80--84. \url{https://doi.org/10.1016/0095-8956(71)90016-5}.
\bibitem{ErdosTriangles} P. Erd\H{o}s, \emph{On a theorem of Rademacher--Tur\'an}, Illinois Journal of Mathematics 6 (1962), 122--127. \url{https://www.renyi.hu/~p_erdos/1962-09.pdf}.
\bibitem{HeHu} F. He and Z. Hu, \emph{A weakly pancyclic theorem for Hamiltonian non-bipartite graphs}, Journal of Systems Science and Mathematical Sciences 28 (2008), 1288--1296. \url{https://doi.org/10.12341/jssms10150}.

\bibitem{Sheehan} J. Sheehan, \emph{Graphs with exactly one hamiltonian circuit}, Journal of Graph Theory 1 (1977), 37--43. \url{https://doi.org/10.1002/jgt.3190010110}.
\bibitem{OSV} F. Nie, H. Ye, S. Liu, Z. Wang, S. Ermon and J. Zou, \emph{One-Sided Verification Under Limited Expert Review}, arXiv:2610.18089 (2026). \url{https://arxiv.org/abs/2610.18089}.
\bibitem{RethlasOSV} S. Liu, \emph{Rethlas-OSV: Desktop Math Agents for Mathematicians}, 29 September 2026, updated 20 October 2026. \url{https://srliu.com/blog/rethlas-osv-guide/}.

\bibitem{LXX} C. Li, L. Xu and B. Zhou,
\emph{The number of cycles of a given length in dense hamiltonian graphs:
proving Hilton's conjecture}, arXiv:2606.16114v1 (15 June 2026).
\url{https://arxiv.org/abs/2606.16114}.
\bibitem{BFG} S. Brandt, R. Faudree and W. Goddard,
\emph{Weakly pancyclic graphs}, Journal of Graph Theory 27 (1998), 141--176.
Author manuscript: \url{https://people.computing.clemson.edu/~goddard/papers/weakpanFinal.pdf}.
\bibitem{Brandt} S. Brandt, \emph{A sufficient condition for all short cycles},
Discrete Applied Mathematics 79 (1997), 63--66.
\url{https://doi.org/10.1016/S0166-218X(97)00032-2}.
\bibitem{EG} P. Erd\H{o}s and T. Gallai,
\emph{On maximal paths and circuits of graphs}, Acta Mathematica Academiae
Scientiarum Hungaricae 10 (1959), 337--356.
\url{https://www.renyi.hu/~p_erdos/1959-10.pdf}.
\bibitem{Kopylov} G. N. Kopylov,
\emph{On maximal paths and cycles in a graph}, Doklady Akademii Nauk SSSR
234 (1977), 19--21; English translation, Soviet Mathematics Doklady 18
(1977), 593--596. \url{https://www.mathnet.ru/eng/dan40958}.
\bibitem{FKLV} Z. F\"uredi, A. Kostochka, R. Luo and J. Verstra\"ete,
\emph{Stability in the Erd\H{o}s--Gallai theorem on cycles and paths, II},
arXiv:1704.02866 (2017). \url{https://arxiv.org/pdf/1704.02866}.
\bibitem{Luo} R. Luo, \emph{The maximum number of cliques in graphs without
long cycles}, arXiv:1701.07472v2 (2017).
\url{https://arxiv.org/pdf/1701.07472}.
\end{thebibliography}
\bigskip
\begingroup\small
\noindent\textsc{Zhili College, Tsinghua University, Beijing 100084, China}\par
\noindent\textit{Email address:}\enspace\mbox{\href{mailto:tangqy24@mails.tsinghua.edu.cn}{\texttt{tangqy24@mails.tsinghua.edu.cn}}}\par
\endgroup
\end{document}