Erdős problem #640: odd cycles whose vertex sets have large chromatic number

Date of investigation: 2026-07-27 UTC

Claim labels

The labels requested in the task are used throughout:

• [a] elementary-rigorous: a complete elementary proof or an explicit finite certificate is given here.
• [b] rigorous-modulo-named-theorem: the claim uses the stated result of a named, checked primary source.
• [c] plausible/structural-unverified: an inference or a negative literature-search result that is not a theorem.
• [d] computational-only: established by the supplied exact program; any external completeness input is stated explicitly.

For a mixed claim, the least self-contained dependency is shown, for example [a+d].

Step 0: authoritative live-page check

[d: live-page observation] I fetched the rendered live page

erdosproblems.com/640 through a Bright Data

browser session on 2026-07-27. The page was marked OPEN, had **0 claimed

proofs**, and showed:

• Currently working on this problem: None
• Interested in collaborating: None
• Likes this problem: Alfaiz
• “This problem looks difficult”: None
• “This problem looks tractable”: None
• “The results on this problem could be formalisable”: None
• “I am working on formalising the results on this problem”: None
• Formalised statement: No

The page said it was last edited 22 January 2026. Thus none of the

mandatory stop conditions was present.

The exact displayed statement is:

> Let \(k\geq 3\). Does there exist some \(f(k)\) such that if a graph \(G\) has chromatic number \(\geq f(k)\) then \(G\) must contain some odd cycle whose vertices span a graph of chromatic number \(\geq k\)?

[d: live-page observation] The page calls this a problem of Erdős and

Hajnal and cites Erdős, Some recent problems and results in graph theory,

p. 84. Its two displayed remarks are:

1. \(k=3\) is trivial, since every non-bipartite graph contains an odd cycle

and every odd cycle has chromatic number 3.

2. Raphael Steiner observed in the comments that replacing “odd cycle” by

“path” gives an equivalent problem.

[d: live-page observation] All three listed comments were inspected:

1. Raphael Steiner (10 August 2025) gives the BFS-layer reduction from the

path formulation to the odd-cycle formulation, with threshold

\(2g(k+1)-1\).

2. ThaDragon195 (22 January 2026) discusses the trivial \(k=3\) case via a

shortest odd cycle.

3. Thomas Bloom (22 January 2026) clarifies that the cycle in the problem is

not required to be induced; imposing “induced” would make the formulation

false for \(k>3\).

What was obtained

[a+d] The original uniform problem is not solved here. The strongest direct result

is the following sharp finite-order theorem.

[d] Finite \(k=4\) theorem. Every graph \(G\) with

contains an odd cycle \(C\) for which

\(\chi(G[V(C)])\geq4\). The chromatic threshold 5 is sharp in this

finite-order regime.

The computation also gives an exact small result for the equivalent path

parameter.

[d] Exact minimum path witness. Up to isomorphism, there is exactly one

graph of minimum order satisfying

Its order is 13. An explicit 13-vertex, 24-edge construction, proof of its

properties, graph6 record, coloring certificates, and an offline exhaustive

checker are given below.

[a] The 13-vertex graph does not improve the elementary lower bound

\(f(4)\geq5\) for the original odd-cycle problem: \(K_4\) already supplies

that bound. Its value is as an exact base case and obstruction for the path

formulation.

Literature check

[b] The original bibliographic record exists as P. Erdős,

Some recent problems and results in graph theory00044-1),

Discrete Mathematics 164 (1997), 81–85. I verified the publisher metadata

and DOI. The attribution of this exact problem to p. 84 comes from the live

page; I did not obtain a searchable copy of that page from the publisher.

[b] A. Gyárfás,

Fruit Salad, *Electronic Journal of

Combinatorics* 4 (1997), R8, states the Erdős–Hajnal odd-cycle problem and

then gives the weaker path conjecture: if every path spans a 3-colorable

subgraph, then the whole graph has bounded chromatic number, perhaps at most

4. This was checked in the primary PDF, not inferred from a citation list.

Define

[b] B. Randerath and I. Schiermeyer,

[*Chromatic Number of Graphs each Path of which is

3-colourable](https://doi.org/10.1007/BF03322762), Results in Mathematics*

41 (2002), 150–155, prove the order-dependent bound

The bibliographic record was checked at the publisher, and the theorem was

cross-checked in the next primary source. Its dependence on \(|V(G)|\) is

exactly why it does not give the uniform function sought here.

[b] B. Cameron and A. Clow,

On Gyárfás' Path-Colour Problem,

arXiv:2506.19100 (2025), restate both problems and prove, constructively, that

for every natural number \(r\) there is a graph with

Consequently any positive uniform answer must allow at least this scale of

separation. They also prove \(\chi(G)\leq2r(G)\) for claw-free graphs and

other bounds for \(K_{1,t}\)-free graphs, and show that graphs with

independence number at most 3 are path-perfect. These are genuine structured

cases, but do not bound arbitrary graphs. The paper explicitly leaves the

principal path conjecture open.

[c] I searched exact phrases from the problem, citations of *Fruit

Salad*, citations of the Randerath–Schiermeyer result, arXiv, Crossref, and

author publication pages through 2026-07-27. I found no later primary source

claiming a resolution after Cameron–Clow. This is an honest search result,

not proof that no such source exists.

Exact reduction to the path problem

Put

and

[a] Lemma 1. \(q(G)\leq r(G)\).

Proof. Delete one edge of a cycle \(C\). What remains is a path on exactly

the same vertex set, so the two induced spans are both \(G[V(C)]\). ∎

[a] Lemma 2. The answer to problem #640 is positive for every \(k\) if

and only if \(h(s)<\infty\) for every integer \(s\). Quantitatively:

for any odd-cycle threshold \(f\), while finite \(h\) gives

Proof of (1). If \(r(G)\leq s\), Lemma 1 gives \(q(G)\leq s\). Hence

\(\chi(G)\geq f(s+1)\) is impossible, proving (1).

Proof of (2), including Steiner's reduction. Define

Then \(\chi(H)\geq g(t)\) forces a path \(P\) in \(H\) with

\(\chi(H[V(P)])\geq t\).

Now suppose \(\chi(G)\geq2g(k+1)-1\), and work in a connected component of

that chromatic number. Take BFS layers \(L_0,L_1,\ldots\). Edges join only

equal or consecutive layers. Therefore the union of the even layers and the

union of the odd layers can each be colored using the maximum number of

colors needed by a single layer. If every layer were

\((g(k+1)-1)\)-colorable, \(G\) would be

\((2g(k+1)-2)\)-colorable. Thus some layer \(L_i\) has chromatic number at

least \(g(k+1)\).

Inside \(L_i\), choose a path \(P\) whose vertex span has chromatic number at

least \(k+1\). If \(P\) has odd length, set \(Q=P\). If it has even length,

delete one endpoint. Deleting one vertex lowers chromatic number by at most

one, so the resulting odd-length path \(Q\) still has

\(\chi(G[V(Q)])\geq k\).

Let \(u,v\) be the ends of \(Q\). Join them to the BFS root along a fixed BFS

tree, and let \(w\) be the last common vertex of the two root paths. The

two tails from \(w\) to \(u\) and \(v\) have equal length, are internally

disjoint, and meet \(Q\) only at \(u,v\), because the internal tail vertices

are in earlier layers. Their union with the odd-length path \(Q\) is

therefore an odd cycle. Its vertex span contains \(G[V(Q)]\), so it has

chromatic number at least \(k\). Finally,

which proves (2). ∎

[a] Consequence. The well-known \(r(G)\leq3\) conjecture, namely

\(h(3)<\infty\), is a necessary consequence of problem #640. It is not by

itself sufficient for the whole problem: the exact equivalence requires

finiteness of every \(h(s)\), and the displayed route to the specific

\(k=4\) odd-cycle case uses \(h(4)<\infty\).

The finite \(k=4\) theorem

[b] The external data are Brendan McKay's

edge-critical graph catalogues,

generated by Olivier Lalonde's open

gencrit program. That page defines

an edge-\(t\)-critical graph as a simple graph with no isolated vertices,

chromatic number \(t\), and chromatic number \(t-1\) after deletion of any

edge. It presents the catalogues as complete through order 13. Catalogue

completeness is an explicit external dependency, not something inferred

from the rows.

[a] Critical reduction. Every graph \(G\) with \(\chi(G)\geq5\) contains

an edge-5-critical subgraph \(H\).

Indeed, choose an edge-minimal subgraph with chromatic number at least 5 and

discard isolated vertices. For every \(e\in E(H)\), minimality gives

\(\chi(H-e)\leq4\). Adding one edge raises chromatic number by at most one,

so \(\chi(H)=5\). Moreover \(\chi(H-e)\) cannot be at most 3, since then

adding \(e\) would make \(H\) at most 4-colorable. Thus

\(\chi(H-e)=4\).

[a] Cycle certificate criterion. Let \(H\) be edge-5-critical of order

\(n\).

• If \(n\) is odd and \(H\) has a Hamilton cycle, that cycle is odd and its

vertex span is all of \(H\), of chromatic number 5.

• If \(n\) is even and \(H\) has a cycle of length \(n-1\), let \(v\) be the

omitted vertex. Then \(\chi(H-v)=4\): it is at most 4 because \(H-v\) is a

subgraph of \(H-e\) for an edge \(e\) incident with \(v\); if it were at

most 3, coloring \(v\) with one fresh color would 4-color \(H\). Thus the

odd \((n-1)\)-cycle has a 4-chromatic vertex span.

[d] Exact scan. The standalone checker downloads and SHA-256-pins every

edge-5-critical catalogue through order 12, decodes every graph6 record, and

uses exact memoized Hamilton-cycle search. It obtained:

| order \(n\) | catalogue size | required odd cycle | failures |

|---:|---:|:---:|---:|

| 5 | 1 | \(C_5\) | 0 |

| 6 | 0 | — | 0 |

| 7 | 1 | \(C_7\) | 0 |

| 8 | 2 | \(C_7\) | 0 |

| 9 | 21 | \(C_9\) | 0 |

| 10 | 162 | \(C_9\) | 0 |

| 11 | 4,008 | \(C_{11}\) | 0 |

| 12 | 147,753 | \(C_{11}\) | 0 |

This is 151,948 independently decoded records in total.

[a+d] Proof of the stated finite theorem. Given an arbitrary

\(|V(G)|\leq12\) with \(\chi(G)\geq5\), take the edge-5-critical subgraph

\(H\) above. It occurs in the applicable complete catalogue. The scan and

cycle criterion give an odd cycle \(C\subseteq H\) with

\(\chi(H[V(C)])\geq4\). Since \(G[V(C)]\) contains \(H[V(C)]\), it too has

chromatic number at least 4.

Sharpness is elementary: \(K_4\) has chromatic number 4, but all its odd

cycles are triangles and their vertex spans are 3-chromatic. Therefore 5 is

the exact finite-order threshold.

Explicit 13-vertex path witness

[a] Construction. Take independent hubs \(a,b,c\), a vertex \(z\), three

vertices \(x_a,x_b,x_c\), and six vertices \(y_{ij}\) indexed by ordered

pairs of distinct hubs. Add exactly these edges:

1. \(z\) is adjacent to all three hubs.

2. \(x_a,x_b,x_c\) form a triangle, and \(x_i\) is adjacent to hub \(i\).

3. \(y_{ij}\) is adjacent to hubs \(i\) and \(j\).

4. For each fixed \(i\), join the two vertices \(y_{ij}\) and \(y_{ik}\),

where \(\{i,j,k\}=\{a,b,c\}\).

There are \(13\) vertices and

\(3+3+3+12+3=24\) edges. The three hubs have degree 6 and the other ten

vertices have degree 3.

For machine interchange, use the vertex order

and graph6 record

L?AA@?O`FsLkE{

[a] Chromatic number 4. In a hypothetical 3-coloring, \(z\) forces the

three hubs to use at most two colors. If all hubs have the same color, the

triangle \(x_a x_b x_c\) would have only the other two colors available,

which is impossible. Otherwise two hubs, say \(j,k\), have one color and

the remaining hub \(i\) has the other. The adjacent vertices \(y_{ij}\) and

\(y_{ik}\) both see the two hub colors and are both forced to use the third

color, another contradiction.

The following explicit 4-coloring, in the displayed vertex order, proves the

upper bound:

(1,1,1,2,2,2,2,2,3,0,0,0,1)

[a] Edge-4-critical certificate. Permuting \(a,b,c\), together with the

corresponding \(x\)'s and ordered-pair \(y\)'s, gives an \(S_3\) group of

automorphisms with six edge orbits. For the numeric order \(0,\ldots,12\)

above, the following are valid 3-colorings after deleting one representative

edge from each orbit:

delete (0,5):  (2,1,1,1,1,2,2,2,2,1,0,0,0)
delete (0,10): (0,1,1,1,1,1,2,2,2,2,0,0,0)
delete (1,6):  (1,2,2,2,2,0,2,0,0,2,0,1,1)
delete (1,10): (0,2,1,1,1,1,1,2,2,2,2,0,0)
delete (1,11): (1,1,2,2,2,0,2,0,0,2,0,1,1)
delete (4,10): (0,1,1,0,2,1,0,2,2,2,2,0,1)

[d] The script verifies the six automorphisms, the orbit partition, these

colorings, and independently finds a 3-coloring after each of all 24 edge

deletions.

[a] No Hamilton path. Deleting the three hubs leaves five connected

components, of orders \(3,2,2,2,1\). Deleting three vertices from a

Hamilton path can leave at most four nonempty path pieces. Every component

of the graph minus the hubs would have to contain at least one such piece,

which is impossible.

[a] Hence \(r(G)=q(G)=3\). Every path misses a vertex. Because the graph

is edge-4-critical, every proper induced subgraph is 3-colorable: for a

missing vertex, choose an incident edge and embed the induced subgraph in

the corresponding edge deletion. Thus every path span is 3-colorable.

The \(x\)-triangle is itself both an odd cycle and the vertex set of a path,

so \(r(G)\geq q(G)\geq3\). Lemma 1 gives \(q(G)\leq r(G)\), proving equality.

[a+d] This structural proof already certifies the main parameters without trusting

an optimizer. As a separate cross-check, the program enumerates all 1,806

path-spanned vertex masks and all simple cycles. It finds maximum path order

12, \(r(G)=3\), 116 distinct odd-cycle vertex masks, 119 even-cycle vertex

masks, and the following numbers of cycles by length:

3:4, 4:9, 5:30, 6:47, 7:72, 8:96, 9:66, 10:18

Every odd-cycle span is independently 3-colored by exact DSATUR search.

Exact minimum and uniqueness for \(r(G)=3<\chi(G)\)

[a] Critical/traceable reduction. A graph \(G\) with

\(\chi(G)\geq4\) and \(r(G)\leq3\) exists on \(n\) vertices if and only if

there is a nontraceable edge-4-critical graph on at most \(n\) vertices.

For the forward direction, take an edge-minimal subgraph \(H\) of chromatic

number at least 4. The same one-edge argument as above makes \(H\)

edge-4-critical. If \(H\) had a Hamilton path, that path in \(G\) would have

vertex span containing the 4-chromatic \(H\), contradicting \(r(G)\leq3\).

For the reverse direction, every path in a nontraceable edge-4-critical

graph misses a vertex and hence has a 3-colorable span.

[d] Catalogue scan. Exact Hamilton-path dynamic programming on the

pinned complete catalogues gives:

| order \(n\) | edge-4-critical graphs | nontraceable |

|---:|---:|---:|

| 4 | 1 | 0 |

| 5 | 0 | 0 |

| 6 | 1 | 0 |

| 7 | 2 | 0 |

| 8 | 5 | 0 |

| 9 | 21 | 0 |

| 10 | 150 | 0 |

| 11 | 1,221 | 0 |

| 12 | 14,581 | 0 |

| 13 | 207,969 | 1 |

The sole nontraceable record at order 13 is the graph6 string above.

[d] Uniqueness among all graphs, not just critical graphs. If a

13-vertex graph \(G\) has \(r(G)\leq3<\chi(G)\), its critical subgraph must

be that sole 13-vertex catalogue graph and therefore spans \(V(G)\). The

checker also tests all 54 missing edges of the witness: every one-edge

extension has a path whose vertex span is not 3-colorable. Any strict

supergraph contains one of these extensions, so it cannot have \(r\leq3\).

This proves the stated catalogue-backed uniqueness up to isomorphism.

[b+d] The existence of nontraceable 4-critical examples is not new—Cameron and

Clow reproduce a Gallai example in their Figure 1—so no novelty is claimed

for that general phenomenon. The useful output here is the symmetric

explicit certificate and the exact catalogue-backed order/uniqueness check.

Reproduction and trust boundary

The standalone checker is

runs/erdos640_wave6h_reverify.py. It uses

only the Python standard library.

Offline witness verification:

python3 runs/erdos640_wave6h_reverify.py

Full pinned-catalogue verification:

python3 runs/erdos640_wave6h_reverify.py --catalog

[d] The offline run constructs the graph from the symmetric definition rather

than trusting graph6; encodes and decodes graph6; checks degrees and edges;

runs exact DSATUR coloring; verifies all edge deletions; runs exact

Hamilton-path DP; enumerates every path-spanned mask and every simple cycle;

checks the hub cut; and checks all one-edge extensions.

[d] The catalogue run downloads the exact files named in the script, rejects a

file unless its SHA-256 digest and row count match the pinned values, then

recomputes every traceability and long-cycle decision from the graph6

records. It does not trust precomputed per-graph answers. Its unavoidable

external assumption is that the host's catalogues are complete up to the

orders claimed. Lalonde's generator is open, and I additionally regenerated

and canonically compared the edge-4-critical catalogues through order 11;

the row sets and counts matched. Regenerating orders 12 and 13 was not done

under the few-CPU-minute constraint. The final full command passed on this VM

in 38.28 seconds wall time with 43,032 KB peak resident memory; the offline

command passed in 3.60 seconds.

Exact wall and next computation

[a] A finite catalogue can prove only a bounded-order statement. The

uniform mathematical obstruction is exactly the finiteness of

for every fixed \(s\). Already \(h(3)<\infty\) is Gyárfás' still-open path

conjecture; current general machinery gives only the

\(|V(G)|\)-dependent logarithmic bound. Even settling \(h(3)\) would not

complete #640: all \(s\) are needed, and the BFS implication for the

specific \(k=4\) case calls for finite \(h(4)\).

[c] The precise missing type of lemma is therefore an

order-independent decomposition or coloring theorem for graphs with bounded

path-span chromatic number. The known forbidden-induced-subgraph results

remove this obstruction only in restricted classes; no checked source

supplies the unrestricted lemma.

[d] The immediate next finite computation is order 13 for the direct

\(k=4\) theorem. McKay's edge-5-critical order-13 catalogue has 8,311,809

records and is about 71 MB compressed. The order-12 phase took about 8.2

single-core seconds here, so a linear first estimate for the same

Hamilton/\((n-1)\)-cycle filter at order 13 is about 460 CPU-seconds

(\(0.13\) core-hours, roughly one cent at a representative

\(\$0.05\)/core-hour before platform minimums). This exceeds the requested

few-CPU-minute budget and was not run. A failure of the long-cycle filter

would require the more expensive exact search over all odd-cycle vertex

sets and their induced chromatic numbers. In contrast, independently

regenerating the order-13 edge-4-critical catalogue, rather than merely

scanning the pinned file, extrapolates to roughly 5.5 core-hours from the

measured small-order generator timings.

PARTIAL: Exact catalogue-backed verification proves the \(k=4\) assertion for every graph on at most 12 vertices, with sharp threshold \(\chi=5\), and determines the unique smallest path-version witness at order 13; the uniform Erdős–Hajnal problem remains open.