Erdős problem #108 — wave 5i

Date: 2026-07-26 (UTC)

Claim labels

• (a) elementary-rigorous: proved here from definitions.
• (b) rigorous-modulo-named-theorem/source: the precise external result or live source is named and linked.
• (c) plausible/structural-unverified: an interpretation, extrapolation, or proposed route, not a theorem.
• (d) computational-only: established by the accompanying finite computation, not used as a uniform proof.

I use \(F(k,r)\) for the least forcing threshold, when it exists. This avoids an ambiguity in the webpage's existential notation \(f(k,r)\): an arbitrary function satisfying the question is not uniquely determined.

Step 0: authoritative live-page check

(b) I fetched the live page through the Bright Data browser on 2026-07-26, before doing mathematics. The page was last edited on 2026-01-23. Its status was OPEN.

(b) Verbatim statement (from the page's own “View the LaTeX source”; only Markdown display delimiters have been added):

For every \(r\geq 4\) and \(k\geq 2\) is there some finite \(f(k,r)\) such that every graph of chromatic number \(\geq f(k,r)\) contains a subgraph of girth \(\geq r\) and chromatic number \(\geq k\)?

(b) The live page lists the source labels [Er71] [Er79b] [Er81] [Er90] [Er95d] [Va99,3.59]. It says the problem was conjectured by Erdős and Hajnal, that Rödl [Ro77] proved the \(r=4\) case (with a link to problem #923), and that the infinite-chromatic-number version remains open. It also records Erdős's [Er79b] question

and links problem #740 for the infinitary version.

(b) The mandatory collision checks were all negative:

• 0 comments;
• 0 claimed proofs;
• “Currently working on this problem: None”;
• “Interested in collaborating: None”.

(b) The remaining displayed markers were: liked by woutercvb; “looks difficult: None”; “looks tractable: None”; “results could be formalisable: None”; and “working on formalising: None”. The page says “Formalised statement? Yes” and “Related OEIS sequences: Possible”. Therefore the stop condition did not trigger.

Verified result

Exact \(k=2\) and \(k=3\) thresholds

(a) Theorem. For every integer \(r\geq4\),

and

Thus \(F(3,4),F(3,5),F(3,6),\ldots=5,5,7,7,9,9,\ldots\).

(a) This exact slice is classical, and I do not claim it as new. Erdős and Hajnal's 1966 odd-cycle theorem implies it, and the June 2026 preprint discussed below explicitly records the same formula. What is supplied here is an independent, short, from-definitions DFS proof and a separate exhaustive checker.

Proof

(a) \(k=2\). Every graph with chromatic number at least \(2\) has an edge. The subgraph consisting of that edge has chromatic number \(2\) and, being a forest, has girth \(\infty\). The one-vertex graph shows that threshold \(1\) fails. Hence \(F(2,r)=2\).

(a) Reduction of \(k=3\) to a long odd cycle. A graph \(G\) contains a subgraph \(H\) with \(\operatorname{girth}(H)\geq r\) and \(\chi(H)\geq3\) if and only if \(G\) contains an odd cycle of length at least \(r\):

• If such \(H\) exists, it is non-bipartite, so it contains an odd cycle; every cycle in \(H\) has length at least \(r\).
• Conversely, retain only the edges of an odd cycle of length at least \(r\). That cycle has chromatic number \(3\) and girth equal to its length.

(a) DFS depth-colouring lemma. Let \(s=s(r)\), the least odd integer at least \(r\), and put \(M=s-1\), which is even. If \(G\) has no odd cycle of length at least \(r\), then \(\chi(G)\leq M\).

Run ordinary depth-first search in every component, obtaining a rooted DFS forest. In an undirected DFS forest, the endpoints of every graph edge are comparable in the ancestor order: if an edge joined two completed branches, its second endpoint would still have been unvisited when the first endpoint was explored and would have become a descendant.

Give a vertex \(v\) the colour

Suppose an edge \(uv\) were monochromatic, with \(u\) the ancestor of \(v\). Then

is a positive multiple of the even number \(M\). The DFS-tree path from \(u\) to \(v\), together with \(uv\), is therefore a simple cycle of length \(d+1\). Its length is odd and at least \(M+1=s\geq r\), a contradiction. Thus this is a proper \(M\)-colouring.

(a) Upper bound. If \(\chi(G)\geq s\), the DFS lemma says that \(G\) cannot avoid all odd cycles of length at least \(r\). The reduction then supplies the required \(3\)-chromatic, girth-\(\geq r\) subgraph. Hence \(F(3,r)\leq s\).

(a) Sharpness. The graph \(K_{s-1}\) has chromatic number \(s-1\). Since \(s-1\) is even, its longest possible odd cycle has length \(s-2<r\). By the reduction it has no subgraph of girth at least \(r\) and chromatic number at least \(3\). Therefore \(F(3,r)>s-1\), completing the equality.

A sharp finite-order refinement

(a) Corollary. Among all \(n\)-vertex graphs containing no odd cycle of length at least \(r\), the maximum chromatic number is exactly

(a) The upper bound is the smaller of the trivial \(n\)-colour bound and the DFS bound. For the lower bound take \(K_{\min\{n,s-1\}}\) plus isolated vertices. Its longest odd cycle has length less than \(r\).

Independent finite verification

(d) The standalone checker is erdos108_wave5i_verify.py. It uses no third-party packages. It:

1. constructs and checks the complete-graph lower-bound certificates for \(4\leq r\leq20\);
2. enumerates all \(33{,}867\) labelled simple graphs on \(1\) through \(6\) vertices;
3. computes each chromatic number exactly by DSATUR-style backtracking;
4. independently recomputes chromatic numbers through five vertices by enumerating every colour assignment;
5. finds longest odd cycles by direct subset/permutation enumeration;
6. constructs the DFS depth-modulo colouring and, for every colour-conflict edge, reconstructs and checks the promised simple long odd cycle;
7. checks the finite-order corollary for every \(4\leq r\leq9\).

(d) Reproduction command:

python3 runs/erdos108_wave5i_verify.py

(d) Observed output:

Predicted exact thresholds:
  f(2,r) = 2 for every r >= 4
  f(3,4) = 5
  f(3,5) = 5
  f(3,6) = 7
  f(3,7) = 7
  f(3,8) = 9
  f(3,9) = 9
  f(3,10) = 11
  f(3,11) = 11
  f(3,12) = 13

Exhaustive finite-order envelope
n r=4 r=5 r=6 r=7 r=8 r=9
1 1 1 1 1 1 1
2 2 2 2 2 2 2
3 3 3 3 3 3 3
4 4 4 4 4 4 4
5 4 4 5 5 5 5
6 4 4 6 6 6 6

labelled graphs checked: 33867
record SHA-256: 87b1e6f68644ae3e33564129bf521f4f99f76f6c45e7872f27f6736c28035fcb
PASS: arithmetic, lower-bound constructions, DFS certificates,
      exact coloring, exact odd-cycle search, and sharp envelopes agree.

(a) The executable core of the DFS certificate is:

s = least_odd_at_least(r)
modulus = s - 1
parent, depth = dfs_forest(adj)
colors = [d % modulus for d in depth]

for u, v in edges(adj):
    if colors[u] == colors[v]:
        ancestor, descendant = orient_by_ancestry(parent, u, v)
        cycle = tree_path(parent, ancestor, descendant)  # close with uv
        assert len(cycle) % 2 == 1
        assert len(cycle) >= s >= r

(d) The linked .py is the complete source, including independent exact-colouring and cycle-enumeration implementations; the schematic excerpt above is not the verifier by itself.

A clean reduction for \(k\geq4\)

(a) Put \(q=k-1\). For a graph \(G\), define its \(q\)-colour defect

and let \(\tau_{<r}(G)\) be the minimum number of edges meeting every cycle of length less than \(r\).

(a) Defect-versus-transversal lemma. If

then \(G\) has a subgraph \(H\) with \(\operatorname{girth}(H)\geq r\) and \(\chi(H)\geq q+1=k\).

Choose a short-cycle transversal \(D\) of size \(\tau_{<r}(G)\) and set \(H=G-D\). It has girth at least \(r\). If \(H\) had a proper \(q\)-colouring, then the same vertex colouring of \(G\) would have all its monochromatic edges in \(D\), giving \(\mu_q(G)\leq |D|=\tau_{<r}(G)\), a contradiction.

(a) If \(\chi(G)=m>q\), then the defect has the general lower bound

Indeed, for a fixed \(q\)-colouring let \(m_i\) be the chromatic number induced by colour class \(i\). Disjoint palettes give \(\sum_i m_i\geq m\). Every \(t\)-chromatic graph has at least \(\binom t2\) edges, by taking a \(t\)-critical subgraph of minimum degree at least \(t-1\). Therefore the number of monochromatic edges is at least

(a) Consequently, the following density-free lemma would be sufficient to settle the full problem by this route:

For every fixed \(q,r\), every sufficiently high-chromatic graph \(G\) has some spanning subgraph \(X\) satisfying \(\tau_{<r}(X)<\mu_q(X)\).

(c) This sufficient lemma is stronger than a mere restatement of the conjecture and is not proved here. It isolates the actual failure of naive edge thinning: one must simultaneously retain a monochromatic edge against every \(q\)-colouring and make all short cycles cheap to hit. Controlling only the expected number of surviving edges or cycles is not enough.

Current literature found and checked

(b) I verified each identifier below against a primary publisher page, paper PDF, or arXiv record and checked that the stated result appears there.

(b) The two 2026 items are not listed in the live page's explanatory text. The SODA result gives a lower bound rather than a solution, and arXiv:2606.17901 explicitly leaves the unrestricted problem open, so neither triggers the “claimed proof / solved / falsified” stop rule.

(c) My searches found no primary source claiming a proof of the unrestricted finite problem. That is a report of the search, not a proof that no such source exists.

Exact wall beyond the small target

(b) Rödl handles \(r=4\), while the polynomial-sparsity preprint claims that any counterexample sequence for fixed \(k,r\) must avoid arbitrarily high-chromatic critical cores whose edge counts are bounded by any fixed power of their chromatic numbers.

(a) The elementary defect lemma shows what must replace sparsity: after some extraction, the cost of hitting every short cycle must be smaller than the minimum monochromatic-edge budget over all \((k-1)\)-colourings.

(c) In a completely unrestricted critical graph, the order and the number and clustering of short cycles can be super-polynomial in its chromatic number. No density-free argument found here forces the required inequality \(\tau_{<r}<\mu_{k-1}\). This is the precise missing lemma for the random-thinning/cycle-deletion route, rather than a vague appeal to “probably open”.

(d) The exhaustive computation deliberately stops at six vertices and does not suggest uniform closure. It took about \(7.9\) seconds for \(33{,}867\) graphs. There are \(2^{28}=268{,}435{,}456\) labelled graphs on eight vertices and \(2^{36}=68{,}719{,}476{,}736\) on nine. Even at the unrealistically favourable measured six-vertex throughput, these are about \(17\) and \(4{,}400\) core-hours respectively; the exact colouring/cycle work per graph also increases with \(n\). Testing all candidate subgraphs for the \(k\geq4\) target adds another exponential layer. I did not run those computations.

(a) More importantly, any finite order cutoff would still need a separate uniformity theorem converting arbitrary-order, high-chromatic inputs to that cutoff. No such reduction is established here.

PARTIAL: Independently proved and exhaustively checked the exact thresholds \(F(2,r)=2\) and \(F(3,r)=r\) for odd \(r\), \(r+1\) for even \(r\), and isolated the density-free short-cycle-transversal versus colour-defect lemma missing for \(k\ge4\); the unrestricted problem remains open.