Hilton’s conjecture on cycle multiplicities

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 [6, 7].

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.

Introduction

Degree and edge conditions that force a Hamilton cycle often also force shorter cycles. Dirac’s theorem [1] states that a graph on $n \ge3$ vertices with minimum degree at least $n/2$ has a cycle through all its vertices. Bondy [2] 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 $\lfloor x \rfloor$ and $\lceil x \rceil$ denote the greatest integer at most $x$ and the least integer at least $x$.

Sheehan’s 1977 paper [5] studies how dense a graph with exactly one Hamilton cycle can be. He proves that the largest possible number of edges is $\lfloor n^2/4 \rfloor+ 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

has at least two cycles of each length $3 \le\ell\le n$. It also records Hilton’s conjecture that

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ős [3]. 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 (1) provide tools for the counting problem. Brandt [10] 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 [9] 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 [4] proved weak pancyclicity for nonbipartite graphs with at least $\lceil n^2/4\rceil-n+12$ edges.

Li, Xu and Zhou [8] proved (2) 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:

$\ell$	6	7	8	9	10
remaining orders $n$	11–38	13–359	15–96	17–439	19–123

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.

The proof uses the counterexample reduction of Li–Xu–Zhou [8 Lemma 3.3]. For an uncovered length, a counterexample would give a spanning Hamiltonian nonbipartite graph with no cycle of that length and with at least $\lfloor n^2/4\rfloor-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)=\lfloor n^2/4\rfloor$ for integers $n \ge0$.

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.

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{a}{b}$ 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.

1. A nonbipartite graph of order $q$ and minimum degree at least $(q+2)/3$ is weakly pancyclic and has girth 3 or 4 [9 Theorem 1.7].

2. A nonbipartite graph of order $q$ with more than $(q-1)^2/4+1$ edges contains every cycle length between 3 and its circumference [10]; see also [9 Theorem 2.12].

3. A graph of order $q$ and circumference at most $c$ has at most $c(q-1)/2$ edges [11 Theorem 2.7].

4. If $J$ is 2-connected, $b=|V(J)|\ge k\ge5$, and $\operatorname{circ}(J)<k$, then

Here $h(b,k,a)$ is defined for integers $b\ge k\ge5$ and $2\le a\le\left\lfloor(k-1)/2\right\rfloor$. This is Kopylov’s bound [12]; an accessible precise statement and a subsequent proof are given in [13 Theorem 1.3] and [14 Theorems 1.3–1.4].

Paths and parity

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.

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$.

Short cycles in dense 2-connected graphs

Proof of Theorem 2. Suppose, for a contradiction, that $H$ satisfies Theorem 2 and has no $C_\ell$.

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

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 $\lfloor(n-i+1)/3\rfloor$. Also, three consecutive integers have floor quotients by 3 summing to the integer minus 1, so $L_3(n)=n-1$. Since $n=q+3$ when $r=3$, we have

Consequently

If $r<3$, then $\delta(R)\ge d:=\lceil(q+2)/3\rceil$.

Bipartite remainder. Assume first that $R$ is bipartite with parts $A,B$ of sizes $a\le b$. Set $k=\lfloor\ell/2\rfloor$, so $3\le k\le5$. For $r<3$ we have $a,b\ge d$, and each pair of vertices in $B$ has at least

common neighbors. Since $q\ge2\ell-3$,

The left-hand side is an integer, so it is at least $\lceil(2\ell+5)/6\rceil$. For $\ell=6,7,8,9,10$, these values are $3,4,4,4,5$, respectively, and are at least $k=\lfloor\ell/2\rfloor$. Each pair in $A$ has at least $2d-b\ge3d-q\ge2$ common neighbors. Also $|B|\ge d\ge k$. Thus Lemma 3 applies.

For $r=3$, put $t=ab-e(R)$, the total number of missing cross edges. Since $a+(b-1)=q-1$, equation (5) gives

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 3 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 4. 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.

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 (5) gives $e(R)\ge(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,

Define the doubled gap

For $n\ge2\ell+1$ and $0\le r\le2$,

The final inequality uses $\lfloor x\rfloor\ge x-1$. Thus $D_r(n)\ge D_3(n)$. Equation (5) gives

At $n=2\ell+1$ this is $\ell-3>0$. Its increment when $n$ increases by one is $2\lfloor(n-3)/2\rfloor-(\ell-1)\ge\ell-1>0$. This contradicts (8) 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

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 $\lfloor2\ell/3\rfloor$, so the same comparison applies. At $n=2\ell-1$, $r=0$ gives $D_0(2\ell-1)=2$. Only the following cases remain:

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

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

In (9), $W\in\{2c-3,2c-2,2c-1\}<2c$.

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

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

The two branches in $B_c(b)$, expanded directly from (4), are

Their maximum gives the first four columns below. The final three columns use (11); for example, $U_5(7)=\max\{10+\binom{3}{2},14\}=14$.

$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)$
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

In particular,

At $n=2\ell-1=2c+1$, the residual bounds simplify to

At $n=2\ell=2c+2$, $M_3(2\ell)=c(c-1)$. Since $5\le c\le9$, the deficit $\left\lceil c/3\right\rceil-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,

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$.

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

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

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

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

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 (13); this excludes $r=1$. At $r=2$, the maximum is $c(c-1)$ and its excess over $M_2(n)$ is $\left\lceil c/3\right\rceil-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$.

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 5 applies. If $\ell=6$, the deficit $\lceil5/3\rceil-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.

Proof of Hilton’s conjecture

Proof of Theorem 1. By Theorem 3.1 of Li–Xu–Zhou [8], 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,

Lemma 3.3 of [8], applied to this construction, gives the additional conclusion that $H$ is nonbipartite. Therefore $H$ is a spanning Hamiltonian nonbipartite $C_{\ell}$-free graph with

The graph $H$ is 2-connected because it contains a Hamilton cycle. Theorem 2 therefore gives $C_{\ell}$ in $H$, a contradiction.

Zhili College, Tsinghua University, Beijing 100084, China

Email address: [email protected]