A Negative Answer to Melnikov's Valency-Variety Problem

The valency-variety w(G) of a graph G is the number of distinct vertex degrees of G. In a problem recorded by Vizing in 1968 and later listed by Jensen and Toft, Melnikov conjectured that every graph G with n ≥ 2 vertices satisfies χ(G) > ⌈⌊w(G)/2⌋/(n − w(G))⌉. We show that the conjecture is false. The inequality is equivalent to (2χ(G) − 1)(n − w(G)) ≥ n − 1. For every k ≥ 3 we construct explicit connected k-chromatic graphs that attain equality in this form, a k-chromatic counterexample on 14k − 5 vertices (it has one isolated vertex), and a connected k-chromatic counterexample on 22k − 9 vertices. A blow-up construction gives connected k-chromatic graphs with n − w = 16n/(32k − 13) < n/(2k − 1), so the inequality fails by an amount that grows linearly in n. On the positive side, the inequality holds for all bipartite graphs, and a counting argument based on Turán's theorem shows n − w ≥ μ_k n − O(1) for every K_{k+1}-free graph, where μ_3 = (3 − √5)/4 ≈ 0.191 (Melnikov's bound asks for 1/5, and our constructions give 16/83 ≈ 0.193). The same argument, evaluated exactly by computer and combined with the bipartite case, shows that every graph with at most 36 vertices satisfies Melnikov's inequality. So the smallest counterexample has 37 vertices. For 3 ≤ k ≤ 60, the smallest k-chromatic counterexample has 14k − 5 vertices, and the smallest one without isolated vertices (in particular, the smallest connected one) has 22k − 9 vertices. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: OPG-46575 (Open Problem Garden, "Melnikov's valency-variety problem").