Deterministic construction of strong thin spanning trees

1 · The essentials

Imagine a finite network of points joined by links, where several links may join the same pair of points but no link joins a point to itself. Suppose that, however you divide the points into two nonempty groups, at least $k$ links run between the groups. The main result says that you can keep enough links to connect all the points without creating any circular routes, while using only a controlled share of the links across every division. That share is at most $C / k$ , where $C$ is one fixed constant that works for all these networks. The statement applies to networks with at least two points and to $k \geq 1$ , and the main result has a Lean formalization. A companion manuscript gives a deterministic method for finding the retained links, with running time polynomial in the length of the input, even when large numbers of repeated links are recorded compactly.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, think of choosing a minimal connected set of roads from a road network, while limiting the share of roads you keep across every possible boundary between two groups of places. The challenge is that the same choice must respect all those boundaries at once, not just one convenient boundary.

Why it matters

The source identifies the existence statement as a resolution of the strong thin-tree conjecture. It combines a requirement to connect the whole network with a bound that must hold across every cut simultaneously. The companion manuscript adds an efficient construction, including for inputs that record parallel-edge multiplicities in binary.

2 · Going further

Let $G$ be a finite loopless multigraph on at least two vertices, and let $k \geq 1$ . Being $k$ -edge-connected means that every cut separating the vertices into two nonempty sets has at least $k$ edges, counting parallel edges separately. Writing $δ_{G} (S)$ for the edges crossing from a vertex set $S$ to its complement, the main statement is that there is a spanning tree $T$ such that $∣ T \cap δ_{G} (S) ∣ \leq (C / k) ∣ δ_{G} (S) ∣$ for every such $S$ , with a universal constant $C$ .

The crucial requirement is simultaneous control: one spanning tree must satisfy the inequality for every cut. The manuscript titled “The strong thin tree conjecture” states this existence result and describes it as resolving that conjecture. The main result has a Lean formalization. The supplied abstract does not describe the argument or its key techniques, so no proof mechanism can be reported from this source.

The companion manuscript, “A polynomial-time construction of strong thin trees,” supplies the algorithmic counterpart: a deterministic polynomial-time construction with a universal $C / k$ cut bound. Its stated input scope includes finite loopless $k$ -edge-connected multigraphs on at least one vertex. Its running-time guarantee is polynomial in binary input length, including when parallel-edge multiplicities are encoded in binary; the supplied information does not identify this algorithmic result as Lean-formalized.

Useful notions

Graphs and parallel edges
Cuts and edge connectivity
Spanning trees
Polynomial running time
Binary encoding

What was known before / what is new

Before

The source names the strong thin-tree conjecture as the problem addressed by the main manuscript. It supplies no account of earlier bounds, partial results, or construction methods, so no more detailed historical comparison is available.

New

The main manuscript establishes the stated universal $C / k$ bound for a spanning tree in every finite loopless $k$ -edge-connected multigraph with at least two vertices and $k \geq 1$ ; this main result has a Lean formalization. The companion manuscript gives a deterministic polynomial-time construction with the same form of guarantee. Its input-length bound explicitly accommodates binary-encoded parallel-edge multiplicities.

Limits and assumptions

The main existence result assumes a finite loopless multigraph, at least two vertices, and $k \geq 1$ . The companion construction states a scope of at least one vertex. The source gives no numerical value for the universal constant C, no details of the argument or algorithm, and no specific polynomial running-time bound. The Lean verification status applies to the main result; formal verification of the companion construction is not stated. No remaining open questions are identified in the supplied text.

Mini glossary

Loopless multigraph: A graph that permits multiple edges between the same pair of vertices but has no edge from a vertex to itself.
Cut: The collection of edges crossing a division of the vertices into two nonempty sets.
k-edge-connected: Having at least k edges in every cut, counting parallel edges separately.
Spanning tree: A selection of edges that connects all vertices without any cycle.
Thin spanning tree: A spanning tree whose number of edges in each cut is bounded by a specified fraction of the original cut size.
Binary-encoded parallel-edge multiplicities: Counts of repeated edges recorded as binary numbers rather than by listing every edge individually.

Keywords : Thin spanning trees · Edge connectivity · Deterministic construction

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Resolves the strong thin-tree conjecture constructively. Every finite loopless k-edge-connected multigraph on at least two vertices has a spanning tree containing at most a universal $C / k$ fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/174.md

Manuscripts in this family

★

The strong thin tree conjecture

23/09/2026

Verified by Lean

We prove that every finite loopless k-edge-connected multigraph on at least two vertices, with k ≥ 1, has a spanning tree meeting each cut in at most $C / k$ times the size of the cut, where C is a universal constant. This resolves the strong thin tree conjecture.

PDF GitHub folder Lean formalization

A polynomial-time construction of strong thin trees

23/09/2026

To be verified

We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a $C / k$ fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.

PDF GitHub folder