Exact Maximums

A graph is a set of dots, called vertices, joined by lines, called edges, and a cycle is a closed path in it. The rank of a graph is its number of edges, minus its number of vertices, plus its number of components. A graph of rank $r$ has fewer than $2^{r}$ cycles.

Let $ψ (r)$ be the largest number of cycles of a graph of rank $r$ . A formula of Horak and Kim gives $ψ (r)$ exactly for every large $r$ . Its first term is $2^{r - 1}$ .

1 The formula

Paper Theorem 1.1, page 2

An even subgraph is a set of edges that meets every vertex an even number of times. A graph of rank $r$ has exactly $2^{r}$ even subgraphs, and each cycle is one of them. In 1981 Entringer and Slater proved that $ψ (r)$ is between $2^{r - 1}$ and $2^{r}$ for $r \geq 3$ . They conjectured that $ψ (r)$ divided by $2^{r - 1}$ tends to 1.

$r$	$2^{r - 1}$	$H (r)$
9	256	380
10	512	696
20	524,288	535,777
27	67,108,864	67,325,913

The first term

2^{r - 1}

and the whole formula

H (r)

Theorem 1.1

For every sufficiently large $q$ ,

\begin{matrix} ψ (2 q + 1) & = 2^{2 q} + (2 q + \frac{1}{2}) 2^{q} - 3 q, \\ ψ (2 q + 2) & = 2^{2 q + 1} + (2 q + \frac{9}{2}) 2^{q} - 3 q - 4. \end{matrix}

Write $H (r)$ for the right sides.

2 Rings of squares

Paper Figure 1, page 2 Proposition 6.1, page 18 Corollary 6.2, page 20

Horak and Kim found graphs with $H (r)$ cycles. A square here has two vertices on its left side, two on its right side, and the four edges between the sides. For an odd rank $r = 2 q + 1$ , put $q$ squares in a ring, and join each square to the next by two edges. For an even rank, add a single rung between two squares: two vertices and the edge between them.

A cycle around the ring takes one of the two edges between each pair of neighbour tiles, and one of two paths through each square. This gives $2^{r - 1}$ cycles. The cycles that do not go around the ring give the other terms of the formula.

For $r = 9$ the formula has $q = 4$ . It gives $256 + 136 - 12$ , which is 380. The ring of four squares has exactly this number of cycles.

3 The first term

Paper Lemma 3.1, page 7 Corollary 3.3, page 7 Forest paper Theorem 1.1, page 2

The degree of a vertex is the number of edge ends at it, and in a cubic graph every vertex has degree three. For the upper limit it is enough to count the cycles of cubic graphs. Remove each vertex of degree one, and replace each vertex of degree two by one edge. Replace each vertex of degree four or more by a path. No step changes the rank, and no step loses a cycle.

A set

P

of four vertices in a ring, and a cycle that meets

P

. Without its dashed edges at

P

, the cycle is a path.

Mark a small connected set $P$ of vertices in a cubic graph. For an even subgraph, the outside part is the set of its edges that have no end in $P$ . A forest is a set of edges that contains no cycle. If a cycle meets $P$ , its outside part is a forest, because it is a cycle without some of its edges.

By the forest estimate, at most a little more than half of all even subgraphs have an outside part that is a forest. Few cycles do not meet $P$ . So

ψ (r) \leq (\frac{1}{2} + \frac{21}{\log \log \log r}) 2^{r},

where $\log$ is the logarithm to the base 2. This proves the conjecture of Entringer and Slater.

4 The second term

Paper Section 1.2, page 3 Figure 2, page 3

The formula is more than $2^{r - 1}$ by about $r 2^{r / 2}$ only. For $r = 27$ that is 217,049 cycles out of 67 million. The error term of the forest estimate is far larger than this. So the second term needs exact arguments. They show that a cubic graph of large rank is a ring, or has at most $2^{r - 1} + K 2^{r / 2}$ cycles. Here $K$ is a fixed number.

A ring here can have squares and single rungs in any order. A cyclic cut is a set of edges whose removal leaves two parts that each contain a cycle. There are three cases.

The graph has a cyclic cut of at most three edges. Then it has at most $2^{r - 1} + K 2^{r / 2}$ cycles.
It has no such cut, and it has a cycle of length four. Then it is a ring, or it has fewer than $2^{r - 1}$ cycles.
It has no such cut and no cycle of length four. Then it has fewer than $2^{r - 1}$ cycles.

5 Paths in a part

Paper Theorem 5.5, page 15 Theorem 5.7, page 16 Proposition 6.3, page 20 Theorem 6.6, page 24

The first two cases divide the graph into parts. A cycle that meets two parts consists of paths in the parts. So the proof counts the paths between two ends $s$ and $t$ of a part. A part of rank $b$ has at most $2^{b}$ such paths.

A ladder of rank 6. It has all

2^{6} = 64

possible paths from

s

t

Two facts hold for every part. If it has more than half of the $2^{b}$ paths, by a fixed margin, then it has at most a fixed number times $2^{b / 2}$ cycles. And if it does not have all $2^{b}$ paths, then a fixed fraction of them is missing. A part with all $2^{b}$ paths is a ladder as in the figure, or a row of ladders.

The first fact uses the forest estimate. Add a shortest path from $s$ to $t$ to any other path from $s$ to $t$ . The sum is an even subgraph, and its edges away from the shortest path form a forest.

In the first case these facts give at most $2^{r - 1} + K 2^{r / 2}$ cycles. In the second case, remove a cycle of length four. If the graph has $2^{r - 1}$ cycles or more, the rest has all possible paths between two pairs of its ends. So the rest is a chain of squares and single rungs, and the graph is a ring. A direct count shows that a ring of rank $r$ has at most $H (r)$ cycles.

6 Girth five

Paper Theorem 7.1, page 25 Lemma 7.5, page 28 Proposition 7.8, page 31

In the third case the graph has no cycle with fewer than five edges. Here the count must end below $2^{r - 1}$ , and the forest estimate cannot give that, because its error term is positive. Mark a connected set $P$ of eight vertices. The claim is that the outside part is a forest for less than $\frac{2}{5}$ of the even subgraphs. Then the graph has fewer than $\frac{2}{5} 2^{r} + 2^{r - 5}$ cycles, which is less than $2^{r - 1}$ .

Two pieces away from

P

. Each piece is large, and few edges leave it.

Suppose that the fraction is $\frac{2}{5}$ or more. Then a second-moment argument finds two disjoint pieces of the graph away from $P$ , each large and with few edges that leave it. In each piece, at most $\frac{3}{5}$ of the possible edge sets are forests, whatever the edges outside the piece are. Two pieces give at most $\frac{3}{5} \cdot \frac{3}{5} = \frac{9}{25}$ , which is less than $\frac{2}{5}$ .

The condition on cycles of length four is necessary. A long ladder has such cycles, and for a ladder the fraction can be 1.

7 Large rank

Paper Section 8, page 35 Fine print after Theorem 1.1, page 3

The formula gives

H (r) \geq 2^{r - 1} + (r - 2) 2^{r / 2 - 1} .

For large $r$ this is more than $2^{r - 1} + K 2^{r / 2}$ . So a cubic graph of large rank with the largest number of cycles is a ring, and $ψ (r) = H (r)$ .

The rank must be large. A generalised Petersen graph of rank 27 has 67,959,973 cycles, and $H (27)$ is 67,325,913. The proof gives no value for the rank from which the formula holds.

KNT directed this work. The language models GPT-6 Astra and Claude Fable 5.2 found the parts of the proof, and Fable 5.2 wrote the paper. A formal copy of the theorem passes Lean, a computer program that checks each step of a proof. Some of its steps are not the steps of the paper. No referee has read the paper.