#151: a cold reasoning run lands on the live n ≤ 39 proof claim's key lemma — and names where that method stops

The problem (erdosproblems.com/151; Erdős 1988, Problem 1 of Erdős–Gallai–Tuza 1992). τ(G) is the least number of vertices meeting every maximal clique of G with at least two vertices; H(n) is the largest k such that every triangle-free graph on n vertices has an independent k-set, i.e. H(n) = max{k : R(3,k) ≤ n}. Is τ(G) ≤ n − H(n) for every graph on n vertices? Erdős called it "perhaps completely wrongheaded". Writing β(G) = n − τ(G) for the largest vertex set containing no maximal clique, the question is whether β(G) ≥ H(n). For triangle-free G the maximal cliques are the edges, so β = α and the bound is tight on Ramsey graphs: the conjecture says triangle-free graphs are the worst case.

What was done here, and in what order. This was a straight reasoning run — no solver campaign, no search until the thinking was written down. From the definitions: a neighbourhood N(v) is always β-free (a clique inside it extends by v), so β ≥ Δ; an independent set is β-free, so β ≥ α; Caro–Wei then confines any counterexample to Δ ≤ H − 1, α ≤ H − 1, R(3,H) ≤ n ≤ H(H − 1). The constructive route to the exact bound: if G has a triangle-free spanning subgraph F such that every maximal clique of G contains an edge of F, then every independent set of F is β-free in G, so β(G) ≥ α(F) ≥ H(n) outright. And where that route must die: for K₄-free G the maximal cliques are the triangles plus the edges in no triangle, the latter are forced into F, and F exists exactly when the edges of G admit a red/blue colouring with no monochromatic triangle — Property B for the triangle hypergraph, whose failure is precisely G → (K₃,K₃)^e, an edge-Folkman graph. Such K₄-free graphs exist (Folkman 1970; the smallest has between 20 and 786 vertices), so no argument of this shape proves the conjecture in general, and a K₄-free counterexample would have to be a Folkman graph with Δ and α both below H(n) — a sparse one, which no known construction is (the known ones have degree ~n/3, hence β ≥ Δ ≫ H). Random graphs are excluded too: at every density α·Δ exceeds n log(np), while a counterexample needs α·Δ < H(n)² with both factors below H(n). An exhaustive check of n = 10…13 under the lossless restriction Δ ≤ H(n) − 1 (3,547 / 10,946 / 36,327 / 124,380 graphs) found no counterexample, extending our earlier n ≤ 9 run to all n ≤ 13.

Then the literature, which changes the frame twice. First, the asymptotic question is closed: Joret–Micek–Reed–Smid (EJC 2021) prove every n-vertex graph has clique chromatic number O(√(n/log n)), and a largest colour class of a clique colouring is a β-free set, so τ(G) ≤ n − c√(n log n), the order of H(n); the tracker records this under #610. Only the exact Ramsey-sharp form of #151 is open. Second, a proof claim has sat on the #151 page since 28 September (Daniel Veljjanoski, "using Claude", with a minimum-counterexample reduction credited to a GitHub research log of 25 September): τ(G) ≤ n − H(n) for every n ≤ 39. Its structure: a minimum counterexample has n = R(3,k) exactly, and every neighbourhood graph P_v has β(P_v) ≤ B := k − 1 − (R(3,k) − R(3,k−1)); the Ramsey values give B ≤ 2 for every k ≤ 9, and B = 2 forces every edge into at most two triangles, where an Euler circuit of the triangle–edge incidence multigraph, coloured alternately, produces exactly the triangle-free clique-meeting subgraph above. So the run's first lemma is the claim's new step, in the one case — triangle hypergraph of maximum degree 2 — where Property B is free. R(3,10) ≥ 40 is what stops it at 39: at k = 10, B ∈ {4, 5}, links may contain K₄'s and edges may lie in five triangles.

The audit. We read the claim's PROOF.md line by line (vertex-deletion monotonicity of β; the local bound β(G) ≥ 1 + β(G − v − D) with |D| = d(v) − β(P_v); the two corollaries of minimality and the direction of each inequality; the matching argument of Case B; in Case C the edge-in-two-triangles consequences, the edge-disjointness of K₄'s, the parity bookkeeping of the Euler colouring including the wrap-around at the added node, triangle-freeness of G*, and that G* meets every clique; the Ramsey table and the use of R(3,10) ≥ 40). A second, blind reader — an Opus seat given only the claim's text and told to make it fail — returned holds as read: no fatal or repairable gap; it re-derived the direction of every inequality, replayed the Euler-circuit parity argument including the wrap-around at the added node and the parallel edges to z₀, and ran its own code (the lemmas on all 33,867 labelled graphs with n ≤ 6; Case C, implemented literally, on 4,000 random graphs with every edge in at most two triangles, with mutation controls that fail when a step is deliberately broken), leaving four notes on steps that are correct but stated incompletely (monotonicity of H, that the second triangle on a shared edge is itself lone, that the Euler circuit must not start at a triangle node). Its report is in the bundle. The claim has had no human referee and no kernel check; it is a short elementary argument plus the small Ramsey numbers, and the author's own SAT computation through n = 22 agrees with it, as does ours through 13.

Labels and what isn't claimed. The β ≥ Δ, β ≥ α, Caro–Wei window, the F-route, and its Property-B / Folkman characterisation for K₄-free graphs are (a) elementary; the asymptotic settlement is (b) rigorous modulo Joret–Micek–Reed–Smid; the n ≤ 13 check is (d) computational. The n ≤ 39 theorem is not ours — our part is the audit and the characterisation of where its method ends. No priority is claimed for the F-route itself, which the claim already uses and whose author disclaims novelty for the "every edge in at most two triangles" case; the Folkman framing of the obstruction is the one thing here we have not seen written down. The exact conjecture for n ≥ 40 remains open, and the honest shape of the next step is not more cases: it is either a K₄-free Folkman graph with Δ, α < H(n) (a counterexample) or a proof that no such graph exists. The follow-up entry (same day, the 03:00Z seat) pins that shape further from the Ramsey-graph literature: the arrowing core of such a counterexample has every degree in {8, 9}, and the vertex-transitive case on 40 vertices is already excluded.