Forest Estimate

A graph is a set of dots, called vertices, joined by lines, called edges. An even subgraph is a set of edges that meets every vertex an even number of times. A cycle is a closed path, and a forest is a set of edges that contains no cycle.

Mark a small set $P$ of vertices in a large graph, and take an even subgraph at random. The forest estimate says that its edges away from $P$ form a forest with a chance of at most a little more than one half.

1 Even subgraphs and outside parts

Paper Section 1.1, page 2 Figure 1, page 2

A cycle meets each of its vertices two times, so it is an even subgraph. 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 exactly $2^{r}$ even subgraphs. A random even subgraph is one of these, each with the same chance.

For a set $P$ of vertices, the outside part of an even subgraph is the set of its edges that have no end in $P$ . Write $q (Γ, P)$ for the chance that the outside part of a random even subgraph of the graph $Γ$ is a forest.

The four even subgraphs, drawn thick. The vertices of

P

are blue, and the outside part is ochre.

The graph in the figure has two triangles and one edge between them. Its rank is 2, so it has four even subgraphs: the empty set, each triangle, and the two triangles together. Let $P$ be the three vertices of the left triangle. The outside part is empty for two of the four, and it is the right triangle for the other two. So $q = \frac{1}{2}$ .

2 The estimate

Paper Theorem 1.1, page 2

Theorem 1.1

Let $Γ$ be a connected graph of sufficiently large rank $r$ in which every vertex has degree at most three. Loops and parallel edges are allowed. Let $P$ be a set of at most $2 r / \log^{2} r$ vertices such that every vertex outside $P$ has degree three. Let the graph on the vertices of $P$ have at most $(\log r) / 100$ components. Then

q (Γ, P) \leq \frac{1}{2} + \frac{20}{\log \log \log r} .

The degree of a vertex is the number of edge ends at it, and $\log$ is the logarithm to the base 2. The term $20 / \log \log \log r$ is less than one half only if $r$ is more than $2^{2^{2^{40}}}$ . So the estimate is a statement about very large graphs, and the proof gives no value for the rank from which it holds.

3 The number one half

Paper Fine print after Theorem 1.1, page 3

The number one half in the estimate cannot be smaller. A square here has two vertices on its left side, two on its right side, and the four edges between the sides. Put $k$ squares in a ring, and join each square to the next by two edges. Every vertex has degree three, and the rank is $2 k + 1$ . Let $P$ be the four vertices of one square.

A ring of four squares. The ochre cycle goes around the ring. Without its dashed edges at

P

, it is a path.

A cycle around the ring takes one of the two edges between each pair of neighbour squares, and one of two paths through each square. This gives $2^{2 k}$ cycles, half of the $2^{2 k + 1}$ even subgraphs. Each of them meets $P$ , so its outside part is a path, and a path is a forest. So $q \geq \frac{1}{2}$ .

Squares	Even subgraphs	Outside part is a forest	$q$
2	32	30	0.938
3	128	106	0.828
4	512	370	0.723
5	2,048	1,314	0.642
6	8,192	4,802	0.586

By the estimate, $q$ tends to one half as the ring grows.

4 Cycles as components

Paper Section 3.2, page 8

Let $ξ$ be the random even subgraph, and let $C$ be a cycle with no vertex in $P$ . Every vertex of $C$ has degree three. So if $ξ$ contains all edges of $C$ , it contains no other edge at $C$ , and $C$ is a whole component of $ξ$ . Then the outside part contains $C$ , and it is not a forest.

The chance of this is at least $2^{- | C |}$ , where $| C |$ is the length of $C$ . For a cycle of length 10 that is 1 in 1024, so many cycles are necessary. The difficulty is that their events are not independent.

5 Links between two cycles

Paper Lemma 2.2, page 5 Lemma 2.3, page 5 Figure 2, page 4

A link between two disjoint cycles is an edge from one to the other. A component of the rest of the graph that is joined to both cycles is also a link. Let two disjoint cycles have $ℓ$ links. Let $p_{1}$ and $p_{2}$ be the chances that the first and the second cycle are components of $ξ$ . Then the chance that both are components is

2^{ℓ - 1} p_{1} p_{2} .

Two links between the cycles

C

and

C^{'}

: an edge, and a component of the rest of the graph. The third component is joined to

C

only.

With one link the two events are independent. With two links the chance of both is two times the product, and the one half of the estimate comes from this factor. A cycle with $d$ edges that leave it has at most $d$ pairwise disjoint partners with three or more links.

For an example, join two triangles by two edges. The graph has rank 3 and eight even subgraphs. Each triangle is a component of two of them, so each chance is $\frac{1}{4}$ . Both triangles are components of one of them, so the chance of both is $\frac{1}{8}$ . That is two times $\frac{1}{4} \cdot \frac{1}{4}$ .

6 The second moment

Paper Lemma 2.1, page 4 Section 4, page 11

Choose a family of cycles away from $P$ , and give each cycle $C$ the weight $2^{- | C |}$ . Let $μ$ be the total weight. Let $Z$ count the chosen cycles that are components of $ξ$ , each multiplied by a factor such that the mean of $Z$ is $μ$ . By the factor 2 of the links, the mean of $Z^{2}$ is at most $2 μ^{2} + 2 μ$ . Then by the Cauchy–Schwarz inequality, the chance that $Z = 0$ is at most

1 - \frac{μ}{2 μ + 2} \leq \frac{1}{2} + \frac{1}{2 μ} .

$μ$	Left side	Right side
1	0.750	1.000
10	0.545	0.550
100	0.505	0.505

The two sides of the inequality for three values of

μ

If the outside part is a forest, then $Z = 0$ . So the estimate holds when the total weight $μ$ is large.

7 The total weight of the cycles

Paper Lemma 2.4, page 6 Lemma 3.3, page 8 Proposition 3.4, page 9

Call a cycle short if it has at most $(\log r) / 10$ edges. Take short cycles away from $P$ one by one, each disjoint from the cycles before, as long as this is possible. If there are $\sqrt{r}$ of them or more, the second moment for these cycles gives the estimate.

In the other case, remove the vertices of $P$ and of these cycles. The graph $J$ that is left has no short cycle, and almost all of its vertices have degree three. A walk that never goes back along its last edge has two ways to continue at such a vertex. So for an even number $ℓ$ between $6 \log r$ and $\log r \sqrt{\log \log r}$ , the graph $J$ has about $2^{ℓ}$ closed walks of this kind with $ℓ$ steps. The paper proves this with an eigenvalue of a matrix.

Most of these walks go one time around a cycle, and a cycle of length $ℓ$ gives $2 ℓ$ of them. So the cycles of length $ℓ$ have a total weight of about $1 / (2 ℓ)$ . The sum over all these lengths gives

μ \geq \frac{\ln \log \log r}{10},

where $\ln$ is the natural logarithm. This grows very slowly with $r$ , and that is why the estimate has the term $20 / \log \log \log r$ .

8 Graphs with larger degrees

Paper Corollary 1.2, page 3 Section 5, page 11

A second form of the estimate has no condition on the degrees. Let $G$ be a connected graph of large rank $r$ without loops and parallel edges. Let $W$ be a union of cycles of $G$ with at most $r / \log^{2} r$ edges and at most $(\log r) / 100$ components. Now the outside part of an even subgraph is the set of its edges that are not in $W$ . It is a forest with a chance of at most $\frac{1}{2} + 20 / \log \log \log r$ .

A vertex of degree five becomes a path of three vertices. The blue edges of

W

end at the first of them, and it goes into

P

For the proof, replace each vertex of degree four or more by a path, and let $P$ be the vertices on $W$ . Away from $P$ , remove each vertex of degree one, and replace each vertex of degree two by one edge. These steps keep the even subgraphs, and the first form applies.

The second form is a step in the solution of Erdős problem 1016. The first form gives the first term of the largest number of cycles of a graph. KNT found the estimate in September 2026 with the language model GPT-6 Astra, and the language model Claude Fable 5.2 wrote the paper. A formal copy of the two forms passes Lean, a computer program that checks each step of a proof. No referee has read the paper.