Erdős problem 738 — live audit, finite census, and exact wall

Date: 2026-07-27 UTC

Claim labels used below:

• (a) elementary-rigorous: proved in the report without an external theorem.
• (b) rigorous-modulo-named-theorem: the stated deduction uses the named published theorem.
• (c) plausible/structural-unverified: a diagnosis or research direction, not a theorem.
• (d) computational-only: exhaustive computation, with its dependency and verifier stated.

0. Mandatory live-page check

(d; direct browser observation.) I fetched the live page through the Bright Data browser path, not datacenter curl: erdosproblems.com/738, accessed 2026-07-27. The page displayed OPEN.

The statement, verbatim as rendered on the live page, is:

> If \(G\) has infinite chromatic number and is triangle-free (contains no \(K_3\)) then must \(G\) contain every tree as an induced subgraph?

(d; direct browser observation.) The other relevant live-page fields were:

• Explanatory text: “A conjecture of Gyárfás.”
• Citation: [Er81] = P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica (1981), 25–42, MR 602413.
• Claimed proofs: 0 claimed proofs for this problem.
• Interested in collaborating: None.
• Currently working on this problem: None.
• Formalised statement: No.

(d; direct browser observation.) The one comment, by Adenwalla at 22:58 on 10 April 2026, says:

> I think this is essentially the Gyárfás-Sumner conjecture, there is a related survey by Scott and Seymour - A survey of \(\chi\)-boundedness.

It links arXiv:1812.07500. The site warns that comments are not verified. I therefore checked the equivalence and the cited literature independently below. Since the page is open, has no claimed proof, and has no current worker, the required stop condition was not triggered.

The live statement does not explicitly insert the word “finite” before “tree.” (b) The cited Gyárfás–Sumner literature treats fixed finite trees and finite host graphs; that is the standard reading analyzed here. Nothing below claims a result about containing arbitrary infinite trees.

1. Exact finite formulation

Fix a finite tree \(T\), and put

(b; de Bruijn–Erdős compactness theorem.) The live question, on the finite-tree reading, is equivalent to

Proof of the equivalence:

1. If \(b(T)=c<\infty\), every finite induced subgraph of an infinite triangle-free \(T\)-free graph is \(c\)-colourable. The de Bruijn–Erdős compactness theorem then makes the whole graph \(c\)-colourable. Thus an infinite-chromatic triangle-free graph cannot be \(T\)-free.

2. Conversely, if \(b(T)=\infty\), choose finite triangle-free induced-\(T\)-free graphs \(H_n\) with \(\chi(H_n)>n\). Their disjoint union is triangle-free and induced-\(T\)-free (a tree is connected), and it has no finite colouring. This contradicts the live statement.

(b) Since triangle-free means \(K_3\)-free, (1) is exactly the clique-number-two case of the Gyárfás–Sumner conjecture.

2. Primary-source literature audit

I searched by the exact conjecture name, the triangle-free specialization, and recent 2024–2026 papers, and then opened the original papers rather than relying on search snippets.

• (b; source-verified.) Scott and Seymour, A survey of \(\chi\)-boundedness, arXiv:1812.07500v3, §3, formulate the Gyárfás–Sumner conjecture as “all forests are \(\chi\)-bounding,” say it remains open for trees in general, and list established families. The survey explicitly works with finite simple graphs.
• (b; source-verified.) Nguyen, Scott, and Seymour, A note on the Gyárfás–Sumner conjecture, arXiv:2302.08922, Conjecture 1.1, again say the conjecture remains open. Their Theorem 1.2 proves the path-induced relaxation: for every rooted tree \((T,r)\) and clique bound, sufficiently large chromatic number forces a copy in which every path starting at \(r\) is induced.
• (b; source-verified.) Scott and Seymour, Polynomial bounds for chromatic number V, arXiv:2202.05557v2, record the Kierstead–Penrice theorem for every tree of radius at most two and prove a polynomial strengthening under a multipartite-subgraph exclusion.
• (b; source-verified.) Nguyen, Scott, and Seymour, Trees and near-linear stable sets, arXiv:2409.09397v2, revised 18 July 2025, prove that a fixed induced forest plus bounded clique number forces a stable set of size \(n^{1-o(1)}\), and obtain a fractional-colouring result for multibrooms. The abstract explicitly says they cannot obtain the linear stable set that the full conjecture would imply.

(c; honest literature assessment.) I found no primary source claiming a proof of the general conjecture or its triangle-free case through the search date. A negative search is not a proof of absence, but it agrees with both the live status and the 2025 primary source. I found no claimed proof to investigate.

3. New verified output of this run: a sharp order-13 census

For a finite tree \(T\), define the bounded-host quantity

Let \(S(a_1,\ldots,a_k)\) be the tree formed from one centre by attaching internally disjoint arms of edge-lengths \(a_1,\ldots,a_k\). Let \(S(2,2)\) in the table mean the double star with two adjacent degree-three centres and two leaves at each centre.

Exact table

(d; exhaustive, dependency: nauty geng 2.8.8, independently rerun.) For every six-vertex tree:

| \(T\) | Canonical description | \(M_{13}(T)\) | A 4-chromatic witness when applicable |

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

| \(P_6\) | six-vertex path | 4 | J?BD@g]Qvo? |

| \(S(1,1,1,2)\) | three unit arms and one length-two arm | 3 | — |

| \(S(1,1,3)\) | arms of lengths \(1,1,3\) | 4 | J?BD@g]Qvo? |

| \(S(2,2)\) | double star, degree sequence \(3,3,1,1,1,1\) | 3 | — |

| \(S(1,2,2)\) | arms of lengths \(1,2,2\) | 3 | — |

| \(K_{1,5}\) | five-leaf star | 4 | K?BD@hWFf_HW |

(d; exhaustive.) Of the eleven nonisomorphic seven-vertex trees,

The graph6 graph J?BD@g]Qvo? is a witness for all ten order-seven types in the second line: among seven-vertex induced trees, it contains exactly \(S(1,1,2,2)\).

This is a sharp finite-host statement only. (a) It does not imply a uniform bound as \(|G|\to\infty\), so it does not settle (1). (b) The four tree types for which the table gives 3 all have radius at most two and are already covered qualitatively (with some finite bound, not this census statement) by the known Kierstead–Penrice family. No novelty claim about the literature is made for the exact values.

Explicit witnesses

(d; checked from the graph6 strings by the standalone decoder.)

• J?BD@g]Qvo? has 11 vertices, 20 edges, degree sequence

\((5,4,4,4,4,4,3,3,3,3,3)\), is triangle-free, is not 3-colourable, and is 4-colourable.

• K?BD@hWFf_HW has 12 vertices, 22 edges, degree sequence

\((4,4,4,4,4,4,4,4,3,3,3,3)\), is triangle-free, is not 3-colourable, and is 4-colourable. Its maximum degree is four, so (a) in a triangle-free graph it cannot contain an induced \(K_{1,5}\).

The standalone verifier decodes these strings without NetworkX and checks all asserted induced-tree exclusions by iterating over vertex subsets.

4. Why the reduced enumeration is exhaustive

The generator was not asked for every triangle-free graph; it generated one representative of every connected triangle-free graph with minimum degree at least three. The reduction to that stream is elementary.

(a) If a finite graph \(G\) is not 3-colourable, choose an induced subgraph \(H\) minimal under vertex deletion subject to not being 3-colourable.

• \(H\) is connected, since otherwise all its components could be 3-coloured separately.
• Every \(H-v\) is 3-colourable. If \(\deg_H(v)\le2\), one of three colours remains for \(v\), a contradiction. Hence \(\delta(H)\ge3\).
• Triangle-freeness and induced-\(T\)-freeness pass to \(H\).

Thus, a triangle-free \(T\)-free counterexample to the upper bound 3 on at most 13 vertices would leave a graph in the generated stream.

(a) The same argument with four colours says that a graph not 4-colourable has a connected vertex-minimal induced subgraph of minimum degree at least four. This is a subset of the minimum-degree-three stream. Therefore checking every stream member that fails the 3-colour test also suffices to prove the global upper bound 4 through order 13.

(a) For every tree in the table, \(C_5\) supplies the lower bound 3: it is triangle-free, 3-chromatic, and has fewer than six vertices.

5. Census and independent checks

Command:

python runs/erdos738_wave6k_verify.py

The verifier:

1. invokes nauty-geng -q -c -t -d3 n;

2. decodes every graph6 line itself;

3. checks symmetry, looplessness, connectedness, triangle-freeness, and minimum degree;

4. runs an exact DSATUR-style \(k\)-colouring backtracker for \(k=3,4\);

5. generates all free trees through order seven by repeated leaf attachment;

6. canonises trees with the AHU centre/parenthesis algorithm and verifies the classical counts \(1,1,1,2,3,6,11\);

7. checks every six- and seven-vertex subset of each retained host; and

8. asserts the table, witness strings, and candidate counts.

(d) The fresh rerun completed with PASS in 89.98 seconds. Its full census was:

| \(n\) | connected triangle-free \(\delta\ge3\) classes | not 3-colourable | not 4-colourable | SHA-256 of raw graph6 stream |

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

| 4 | 0 | 0 | 0 | e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 |

| 5 | 0 | 0 | 0 | e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 |

| 6 | 1 | 0 | 0 | 4460415c2b5304b000285c2d117e72363a20c92c28c2575b8bd88dba91646230 |

| 7 | 1 | 0 | 0 | 08d2b049f74e1a7e3e491644b5b631162e246edda54242759868f5974cf23623 |

| 8 | 8 | 0 | 0 | aeee32545e12442481d005824827f013006bf370ff1e25ccac4e10228ecb788a |

| 9 | 23 | 0 | 0 | b09213df5da5f111a29e219389745a4aacd8f86a98b5d50c09b01eea17c6bf3a |

| 10 | 209 | 0 | 0 | 66c1896a42c22af5168040cfdd15379d3d08a08d38b92bcffa006d73e52a9a1b |

| 11 | 2,052 | 1 | 0 | b532df39d81c1175fb29808eef530e23fbe8381d6dbbfccdd61f578c2af94ca3 |

| 12 | 36,223 | 14 | 0 | 3bc51b18efc6a6a15eaf4e1c6745ce6a19f171dfc45cfc1b7e6c8799e739cc23 |

| 13 | 874,997 | 487 | 0 | 08ceb26096cd5d7b11709fa920e9b34b5ebc729215c685cd6c34d694736ede48 |

There are 502 retained non-3-colourable hosts. (d) Their avoidance counts for the three six-vertex types having a 4-chromatic witness were:

| \(T\) | order 11 | order 12 | order 13 | total |

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

| \(P_6\) | 1 | 4 | 19 | 24 |

| \(S(1,1,3)\) | 1 | 1 | 2 | 4 |

| \(K_{1,5}\) | 0 | 3 | 3 | 6 |

For each of \(S(1,1,1,2)\), \(S(2,2)\), \(S(1,2,2)\), and \(S(1,1,2,2)\), the avoidance count was zero.

The complete executable code is in runs/erdos738_wave6k_verify.py. It uses no saved census and recomputes every row. python -m py_compile and git diff --check also passed.

6. Exact wall and next computation

(b; Nguyen–Scott–Seymour Theorem 1.2.) Large chromatic number with bounded clique number already forces a path-induced copy of every rooted tree. In such a copy, every unwanted extra edge has endpoints that are incomparable in the rooted ancestor order: an ancestor–descendant extra edge would chord a root path. (a) In a triangle-free host, two children of the same parent cannot be joined either, since that would make a triangle.

(c) The remaining structural obstruction is therefore precise: cross-edges between more remote, incomparable branches. A lemma that selects the required branches while eliminating all such cross-edges, without losing unbounded chromatic number, would upgrade the path-induced theorem to problem 738. The cited machinery does not supply that branch-cleaning/independent-transversal step; asserting that it does would simply assume the open conjecture.

(d) A count-only nauty run found 29,123,001 connected triangle-free minimum-degree-three isomorphism classes at order 14; generation alone took 75.30 seconds. Scaling the fully validating Python pipeline by the observed order-13 throughput gives roughly \(0.8\) core-hours for the complete order-14 colour/profile pass. That exceeds the few-minute budget, so it was not run. Even completing it would move only the finite cutoff from 13 to 14 and would not provide the uniformity needed in (1).

PARTIAL: The open problem is not solved; an independently rerun exhaustive census proves the exact values of \(M_{13}(T)\) for every 6- and 7-vertex tree, with explicit 4-chromatic graph6 witnesses and a precise cross-branch cleaning lemma identified as the uniform obstruction.