WorksMathematics
A counterexample to Erdős problem 108 via arc graphs
Abstract
For every positive integer , we construct a finite triangle-free graph of chromatic number at least in which every ordinary four-cycle-free subgraph is 6-colorable. Consequently, no chromatic threshold forces a subgraph of girth at least five and chromatic number at least seven, which gives a negative answer to Erdős problem 108. The proof uses a multipartite random graph of bounded acyclic outdegree in which every subgraph under a prescribed degree cap is 4-colorable. An arc-graph construction raises the host chromatic number while partitioning each four-cycle-free subgraph into a part controlled by the degree cap and a forest. The linked Lean verification covers the original negative answer. The written proof includes the triangle-free strengthening.
Introduction
The high-girth subgraph problem of Erdős and Hajnal asks whether, for every pair of integers and , there is an integer such that every graph of chromatic number at least contains a subgraph of girth at least and chromatic number at least . The question appears as Problem 108 in Bloom’s catalogue [1] and is formalized in the Formal Conjectures library [2].
Throughout this paper, a subgraph may be obtained by deleting vertices and edges. A four-cycle-free graph excludes a copy of as an ordinary subgraph. A four-cycle with chords is still forbidden.
Theorem 1.1. For every integer , there is a finite nonempty triangle-free simple graph such that and every four-cycle-free subgraph of satisfies .
Corollary 1.2. There is no integer such that every graph of chromatic number at least contains a subgraph of girth at least five and chromatic number at least seven. In particular, the assertion in Erdős problem 108 is false.
Proof. Given a proposed threshold , apply Theorem 1.1 with . Every subgraph of girth at least five is four-cycle-free, so its chromatic number is at most six.
The construction starts with the multipartite random model used by Janzer, Steiner and Sudakov in their work on chromatic number and regular subgraphs [3]. We adapt its separated-part-size method to obtain a statement with two independent parameters, a chromatic parameter and a degree cap . The outdegree bound depends only on . This permits us to choose after fixing that bound and then apply an arc-graph argument. All estimates needed for this adaptation are proved here.
Section 2 gives the arc-graph lemmas. Section 3 constructs the base graph, including the size estimates and both probability bounds. Section 4 proves Theorem 1.1. Section 5 describes the formal proof and its verification records.
Notation. All graphs used in the construction are finite and simple. We write for the number of edges in , and for the number of edges between disjoint vertex sets and . The maximum degree of a graph is denoted by . A graph is 3-degenerate if every nonempty subgraph has a vertex of degree at most three. Such a graph is 4-colorable. For an acyclic digraph , let be its underlying undirected graph. Forests have infinite girth in the written proof.
Arc graphs and bounded-degree selections
Definition 2.1. Let be an acyclic orientation of a simple graph. Its arc graph has the arcs of as vertices, with two vertices adjacent precisely when the corresponding arcs concatenate. Thus and are adjacent. We orient this edge from to .
Fix a topological ordering of . Along every oriented edge of , the tail of the corresponding arc strictly increases in this ordering. The displayed orientation of is therefore acyclic.
Lemma 2.2. The graph is triangle-free.
Proof. An acyclic orientation of a triangle has vertices with edges , and . If and , the edge makes the tail of equal to , whereas makes it equal to . Hence , contradicting the fact that is an arc of a simple graph. □
Lemma 2.3. If is -colorable, then is -colorable. In particular,
Proof. Fix a proper coloring of with colors in . Assign to each vertex of the set of colors occurring on arcs directed out of . If has color , the set at contains . Every arc directed out of is adjacent to , so the set at excludes . Adjacent vertices of therefore receive distinct subsets of the -element color set. □
Lemma 2.4 (Arc selection). Suppose that is acyclic, has maximum outdegree at most , and every subgraph of with maximum degree at most
is -colorable. Then every four-cycle-free subgraph of is -colorable.
Proof. Let be four-cycle-free, and restrict the natural orientation to . Partition its vertex set into and , where consists of the arc vertices having at least two outgoing neighbors in , and consists of the remaining arc vertices.
Fix a vertex of . For every incoming arc belonging to , choose an unordered pair of its outgoing neighbors in . These neighbors are arcs of the form . Two distinct incoming arcs cannot receive the same pair, since the two incoming arcs and the two chosen outgoing arcs would form a four-cycle. Consequently at most
incoming arcs at belong to .
Let retain precisely the arcs of corresponding to vertices in . Its outdegrees are at most and its indegrees are at most . Hence . By hypothesis there is a proper -coloring of . Color an arc vertex by . If and are adjacent in , the edge belongs to , so these two arc vertices receive different colors.
The inherited orientation of is acyclic and every vertex has outdegree at most one. Such a graph is a forest. In an acyclic orientation any undirected cycle has a source on that cycle and therefore a vertex with two outgoing edges. Color with two colors disjoint from the first palette. This gives an -coloring of . □
Remark 2.5. The partition and the selected graph depend on the edge-deleted subgraph . The argument works for ordinary subgraphs. The indegree bound applies to the selected digraph .
The multipartite base graph
Theorem 3.1. For every pair of integers and , there is a finite simple graph with an acyclic orientation such that
,
the maximum outdegree of is at most , and
every subgraph with is -degenerate, and hence -colorable.
In particular, the outdegree bound in (2) is independent of .
The random model and explicit sizes
Put
Choose the positive integer , then define and the part sizes by
Take disjoint sets with and no edges inside a part. For every and every , independently choose a uniformly distributed vertex and insert the edge . Orient each edge from its earlier part to its later part. This orientation is acyclic and has maximum outdegree at most .
Write and . The following elementary estimates are the reason for the choice of exponents.
Lemma 3.2. The sizes in (5) satisfy
For , put . For every integer with , one also has
Proof. Since and , the exponent is a positive integer. For the two exponents differ by at least one, which proves (6). The sizes are decreasing. Since and each , we obtain . The other inequalities in (7) use . Moreover, for each , so , proving (8).
Fix . Since , the successive-size inequality gives . Next, the identity gives
Thus . It follows that
where the last inequality is immediate from (4).
The deterministic cut
Consider the following local sparsity condition on a realization of :
For the condition is vacuous.
Lemma 3.3. If (10) holds for every , then every subgraph of with maximum degree at most is -degenerate.
Proof. Suppose that has minimum degree at least four and maximum degree at most , and let . By (7), there is an index with . Choose the largest such index. Partition into , according as the part index is less than, equal to, or greater than . If , then . Otherwise, maximality gives , and the decreasing sizes give . In either case we may use the weaker bound
Each vertex of has at most one neighbor in , while the degree cap gives at most edges incident with . Hence and . Taking the weighted average with weights and yields
The set is independent. At most edges have an endpoint in , and the minimum-degree assumption gives . Therefore
In particular is nonempty, and . Since , this contradicts (10). Thus there is no subgraph with all degrees between four and . Every subgraph of a graph of maximum degree at most still has maximum degree at most , so every such graph is -degenerate. □
The probability of a dense earlier set
Lemma 3.4. The probability that (10) fails for some is at most .
Proof. Fix and , and put , , and . For a specified collection of distinct possible edges among the earlier parts, either two edges demand different choices from the same pair , in which case the event is impossible, or they impose independent choices. Every target part has size at least , so the probability that all the specified edges occur is at most .
There are at most possible sets of size , and at most choices of the required edges. Thus the probability that an earlier set of size violates (10) is at most
Here we used for , together with . If the prescribed number of edges is impossible, the same estimate holds with probability zero.
Set and . By Lemma 3.2, . Since , raising the right side of (14) to the integer power gives
It follows that (14) is at most . Since , summing over the possible positive sizes gives a failure probability at most
for a fixed . Summing over at most indices proves the result.
The probability of a heavy independent set
Assign weight to each vertex of . For a vertex set , write
The total vertex weight is .
Lemma 3.5. The probability that has an independent set with is at most .
Proof. Suppose that . Choose the first index with . Such an index exists. Earlier parts contribute less than and , so
The part of in indices at least is still independent and preserves both inequalities. We may therefore count only sets in this suffix.
Fix a suffix set satisfying these inequalities, and put . For to be independent, all choices from its vertices in to each later part must avoid . These choices are independent, so
Indeed, (16) and give an exponent of absolute value at least . By (8), the entire suffix has at most vertices. There are therefore at most possible suffix sets. The union bound and (17) give probability at most for a witness with a fixed first heavy index . Finally, and imply . Summing over all proves the lemma.
Proof of Theorem 3.1. Lemmas 3.4 and 3.5 bound the two failure probabilities by each. Their sum is less than one, so there is a realization satisfying (10) in which every independent set has weight less than . Lemma 3.3 proves (3), and the orientation of the construction proves (2).
If were -colorable, its color classes would be independent sets of total weight strictly less than . But the color classes partition a vertex set of weight . This contradiction proves , completing (1).
Proof of the main theorem
Proof of Theorem 1.1. Fix and put
These parameters satisfy and . Apply Theorem 3.1 with this pair to obtain . Every subgraph of with maximum degree at most is -colorable, and the maximum outdegree of is at most . The choice of is legitimate because the outdegree bound in Theorem 3.1 is independent of . Set . Lemma 2.4, with , shows that every four-cycle-free subgraph of is 6-colorable. Lemma 2.2 shows that is triangle-free. If , then Lemma 2.3 gives
contrary to Theorem 3.1. Thus . The graph is finite, and this inequality also ensures that it is nonempty. □
Remark 4.1. List the vertices of in a topological order. The map sending an arc to the ordered pair of its endpoint indices identifies with an induced subgraph of the canonical shift graph on ordered pairs with , where is adjacent to . The proof of Corollary 1.2 uses only the conclusions of Theorem 1.1.
Lean formalization and verification
The accompanying source edition [5, 6] formalizes the arc-graph construction and the negative answer. The theorem Bounty.arc_counterexample_family gives a nonempty arc-graph witness for each , with chromatic number at least and with every four-cycle-free subgraph 6-colorable. The triangle-free conclusion of Theorem 1.1 follows from Lemma 2.2 in the written proof. The checked Bounty.target proves the negation of the original Erdos108.erdos_108 type.
The formalization represents vertices of the multipartite model as pairs with and , in lexicographic order. A sample is a finite dependent product of choices. Unused choices into earlier parts are retained so that the sample space is rectangular. Uniform probabilities are finite-set cardinalities divided by the cardinality of the sample space. The existence argument uses exact finite counting and real-valued estimates in Lean.
The predicate FourCycleFree excludes two distinct vertices having two distinct common neighbors. In a simple graph this is exactly the absence of an ordinary four-cycle. The type SimpleGraph.Subgraph includes both vertex and edge deletions. A graph relation on the same vertex type permits edge deletions and can represent vertex deletions by treating the deleted vertices as isolated.
Table 1 lists the selected correspondences. The Lean proof establishes the 4-colorability conclusion of Theorem 3.1 directly by finite-set induction using the low-degree vertex supplied by the cut argument. The library chromatic number takes values in the extended natural numbers. Its natural-valued girth is zero for an acyclic graph, whereas the written proof assigns infinite girth to forests. The formal proof uses the implication from library girth at least five to four-cycle-freeness. The statement about four-cycle-free subgraphs also covers forests. The final family is transported by ULift to the universe quantified over by the target.
| Mathematical statement | Lean declaration |
| Lemma 2.3 | base_colorable_of_arc_colorable |
| Lemma 2.4 | arc_subgraph_colorable_bound |
| Lemma 3.2 | model_sizes_exist |
| Lemma 3.3, coloring conclusion | colorable_four_of_sparse_cuts |
| Lemma 3.4 | model_badSparse_probability_le |
| Lemma 3.5 | model_badColor_probability_le |
| Theorem 3.1, needed conclusions | model_base_exists |
| Theorem 1.1, family and coloring | arc_counterexample_family |
| Corollary 1.2, pinned target | target |
Table 1. Selected correspondences with the submitted Lean file. Declaration names lie in namespace Bounty.
Pinned environment and scope of verification. The supplied checks use Lean 4.33.1 [4], mathlib revision 0df444a360ea, and Formal Conjectures task revision 8432eac99811. The unwrapped proof ends with the declaration below, where Not is written as Lean’s negation symbol.
theorem target : Not (fcTypeOfName% "Erdos108.erdos_108") := by
exact counterexample_of_family counterexample_family
The task’s type extractor supplies the statement. The local axiom audit for Bounty.target reports exactly propext, Classical.choice, and Quot.sound. The pinned source edition supplies the accepted proof body, the task wrapper, and the local build log and digest [5]. Conjectures.io records production verification and public certification of the negative answer [6]. These records apply to the original target. The original manuscript [7] names two additional Lean declarations for the triangle-free strengthening. The source documentation records that those declarations are absent from the supplied proof [8].
Concluding remarks
The obstruction is uniform. The bound six does not depend on the chromatic number of the host graph. Hence the same family excludes a threshold for every girth parameter at chromatic parameter . The argument does not establish whether six is the smallest possible uniform bound.
The sizes in (4)–(5) were chosen to simplify the proof and its formalization. They specify a finite construction, but are far too large to make enumeration of the required realizations practical. The conclusion is an existence theorem proved by the finite probability estimates above.
Acknowledgements and AI-use disclosure. This work was developed with substantial assistance from OpenAI ChatGPT/Codex, including mathematical exploration, the preparation and checking of estimates, construction and debugging of the Lean proofs, and drafting and typesetting of the manuscript. Jensen Kohlmeyer and Liam Kruer are responsible for the mathematical content and its presentation. The formal source and the verification record make the machine-checked claims inspectable.
References
- [1]T. F. Bloom, Erdős Problem #108, Erdős Problems.
- [2]Google DeepMind and contributors, Formal Conjectures, file FormalConjectures/ErdosProblems/108.lean, repository. The task revision is specified in Section 5.
- [3]B. Janzer, R. Steiner and B. Sudakov, Chromatic number and regular subgraphs, Bull. London Math. Soc. (2026), DOI, preprint arXiv:2410.02437.arxiv.org/abs/2410.02437
- [4]Lean community, The Lean 4 theorem prover, version 4.33.1.
- [5]Pinned original-source edition and verification report.
- [6]Conjectures.io, Erdős problem 108, production verification record.
- [7]J. Kohlmeyer and L. Kruer, Original arc-graph manuscript, September 15, 2026, linked from Justin Sun Prize submission JSP-000120.
- [8]Source notes on manuscript correspondence, pinned at the manuscript revision.