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-2s-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_{

(a) Defect-versus-transversal lemma. If