HEXAGONbeta

Tools for proving that graphs are not graceful

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricscs.DM — Discrete Mathematics

Contributed by Boon Suan Ho

Version 1 / Oct 17, 2026 / CC BY 4.0

Abstract

A graph with mm edges is graceful if its vertices can be labeled with distinct integers in [0,m][0,m] whose edge differences are exactly 1,…,m1,\dots,m. Graceful labelings have been constructed for sixty years, but there are few general methods for showing that a graph is not graceful. We start from a single generating-function identity that restates gracefulness, and derive three tools from it: residues at roots of unity, extending the classical parity condition; positivity on the unit circle, whose semidefinite form amounts exactly to the Goemans–Williamson max-cut relaxation tested against the minimum of the Dirichlet kernel; and the label interval itself, which forces the labels of a dense subgraph to have a large span. The consequences include new families of ungraceful graphs: every edge-transitive graph that contains K6K_6, the Paley graphs P(q)P(q) with q≥37q\ge37, the Kneser graphs K(n,k)K(n,k) with n≥5.61kn\ge5.61k, almost every dd-regular graph with d≥84d\ge84, and the polarity graphs ERq\mathrm{ER}_q with q≥23q\ge23, which contain no 44-cycle. For the semidefinite form of positivity we also determine exactly what it can prove, and we show that a planar refinement is strictly stronger: it excludes the Kneser graph K(11,2)K(11,2) with any seven edges deleted.

Provenance statement

The text of this paper was written entirely by Claude Opus 5.5 (Anthropic), at the direction of Boon Suan Ho, who chose the questions and steered the work over several sessions. Results marked with a star in the paper were found by Claude in this collaboration; results marked with a dagger were found by GPT-6 Pro (OpenAI), mostly in a referee report on an earlier draft. Claude also ran the literature searches, independent reviews of the draft, and exact computations (Python, OR-Tools CP-SAT, and exhaustive searches in C) to check the finite claims and numerical thresholds. The author has not checked every proof in detail. Section 6 of the paper records the provenance of each result.

Tools used

Anthropic
Claude OpusVersion 5.5
OpenAI
ChatGPTVersion GPT-6 Pro
Anthropic
Claude Code

References

  1. J. Abrham, Perfect systems of difference sets---a survey, Ars Combin. 17A (1984), 5--36.
  2. J.-C. Bermond and G. Farhi, Sur un problème combinatoire d'antennes en radioastronomie II, Ann.\ Discrete Math. 12 (1982), 49--53; 10.1016/S0304-0208(08)73490-X.DOI
  3. J.-C. Bermond, A. Kotzig and J. Turgeon, On a combinatorial problem of antennas in radioastronomy, in Combinatorics (Keszthely, 1976), Colloq.\ Math.\ Soc.\ János Bolyai 18, North-Holland, 1978, 135--149; https://hal.science/hal-02322841.link
  4. J.-C. Bermond, Graceful graphs, radio antennae and French windmills, in Graph Theory and Combinatorics , Pitman, London, 1979, 18--37.
  5. A. Bernshteyn and M. Tait, Improved lower bound for difference bases, J. Number Theory 205 (2019), 50--58; 10.1016/j.jnt.2019.05.002; 1901.09411 .DOI
  6. T. Beth, D. Jungnickel and H. Lenz, Design Theory , 2nd ed., Cambridge University Press, 1999.
  7. D. Beutner and H. Harborth, Graceful labelings of nearly complete graphs, Results Math. 41 (2002), 34--39; 10.1007/BF03322754.DOI
  8. B. Bollobás and O. Pikhurko, Integer sets with prescribed pairwise differences being distinct, European J. Combin. 26 (2005), 607--616; 10.1016/j.ejc.2004.04.008.DOI
  9. J. Briët, F. M. de Oliveira Filho and F. Vallentin, Grothendieck inequalities for semidefinite programs with rank constraint, Theory Comput. 10 (2014), 77--105; 10.4086/toc.2014.v010a004.DOI
  10. A. E. Brouwer and W. H. Haemers, Spectra of Graphs , Springer, 2012; 10.1007/978-1-4614-1939-6.DOI
Show all 48 referencesShow fewer references
  1. N. G. de Bruijn, On number systems, Nieuw Arch.\ Wisk. (3) 4 (1956), 15--17.
  2. A. Burgess, F. Merola and T. Traetta, On circular external difference families, preprint, 2509.02731 , 2025.
  3. P. J. Cameron, J.-M. Goethals, J. J. Seidel and E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), 305--327; 10.1016/0021-8693(76)90162-9.DOI
  4. D. Carter, Z. Hunter and K. O'Bryant, On the diameter of finite Sidon sets, Acta Math.\ Hungar. 175 (2025), 108--126; 10.1007/s10474-024-01499-8.DOI
  5. Y. M. Chee and C. J. Colbourn, Constructions for difference triangle sets, IEEE Trans.\ Inform.\ Theory 43 (1997), 1346--1349; 10.1109/18.605606.DOI
  6. J. Clark, B. Curtis, E. Gnang and L. Hogben, Apportionable matrices and gracefully labelled graphs, Linear Algebra Appl. 698 (2024); 2308.11808 ; 10.1016/j.laa.2024.06.001.DOI
  7. C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math.\ Programming 62 (1993), 557--574; 10.1007/BF01585184.DOI
  8. M. Ferrara, Y. Kohayakawa and V. Rödl, Distance graphs on the integers, Combin.\ Probab.\ Comput. 14 (2005), 107--131; 10.1017/S0963548304006637.DOI
  9. J. Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Mem.\ Amer.\ Math.\ Soc. 195 (2008), no. 910; 10.1090/memo/0910.DOI
  10. J. A. Gallian, A dynamic survey of graph labeling, Electron.\ J. Combin. , Dynamic Survey DS6, 28th ed., 2025; https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.link
  11. G. Ge, Y. Miao and X. Sun, Perfect difference families, perfect difference matrices, and related combinatorial structures, J. Combin.\ Des. 18 (2010), 415--449; 10.1002/jcd.20259.DOI
  12. C. Godsil, D. E. Roberson, B. Rooney, R. Šámal and A. Varvitsiotis, Universal completability, least eigenvalue frameworks, and vector colorings, Discrete Comput.\ Geom. 58 (2017), 265--292; 10.1007/s00454-017-9899-2.DOI
  13. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), 1115--1145; 10.1145/227683.227684.DOI
  14. S. W. Golomb, How to number a graph, in Graph Theory and Computing (R. C. Read, ed.), Academic Press, 1972, 23--37; 10.1016/B978-1-4832-3187-7.50008-8.DOI
  15. B. S. Ho, answer to ``Do the windmills K5(3)\smash[t]{K_5^{(3)}} and K5(4)\smash[t]{K_5^{(4)}} admit graceful labellings?'' (question by R. J. Stones, with comments by B. D. McKay), MathOverflow, June 2022, https://mathoverflow.net/q/424682.link
  16. D. E. Knuth, Changes to The Art of Computer Programming, Volume 4, Fascicle 7: Constraint Satisfaction , ``Breaking News'', answer to exercise 81 (amendment dated 10 October 2026), https://www-cs-faculty.stanford.edu/~knuth/err4f7.textxt.link
  17. D. E. Knuth, Coups de grâceful graphs, unpublished note, 2020, revised 2026, https://cs.stanford.edu/~knuth/papers/coups.pdf.link
  18. D. E. Knuth, The Art of Computer Programming , Volume 4, Fascicle 7: Constraint Satisfaction , Addison-Wesley, 2025.
  19. K. M. Koh, D. G. Rogers, H. K. Teo and K. Y. Yap, Graceful graphs: some further results and problems, Congr.\ Numer. 29 (1980), 559--571.
  20. A. Kotzig and J. Turgeon, β\beta-valuations of regular graphs with complete components, in Combinatorics (Keszthely, 1976), Colloq.\ Math.\ Soc.\ János Bolyai 18, North-Holland, 1978.
  21. A. Kotzig and J. Turgeon, Regular perfect systems of difference sets, Discrete Math. 20 (1977), 249--254; 10.1016/0012-365X(77)90064-4.DOI
  22. P. J. Laufer, Regular perfect systems of difference sets of size 4 and extremal systems of size 3, Ann.\ Discrete Math. 12 (1982), 193--201; 10.1016/S0304-0208(08)73504-7.DOI
  23. J. Leech, On the representation of 11, 22, , nn by differences, J. London Math.\ Soc. 31 (1956), 160--169; 10.1112/jlms/s1-31.2.160.DOI
  24. B. Lindström, An inequality for B2B_2-sequences, J. Combin.\ Theory 6 (1969), 211--212; 10.1016/S0021-9800(69)80124-9.DOI
  25. H. Liu, T. Feng, X. Wang and M. Zhang, Perfect difference families, perfect systems of difference sets and their applications, J. Combin.\ Theory Ser. A 223 (2026), 106199; 2510.20446 ; 10.1016/j.jcta.2026.106199.DOI
  26. A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261--277; 10.1007/BF02126799.DOI
  27. C. Ma and X. Yi, An almost-covering threshold for Golomb-ruler difference packings, preprint, 2608.13739 , 2026.
  28. R. Mathon, Constructions for cyclic Steiner 22-designs, RIMS Kôkyûroku 607 (1987), 22--32.
  29. B. Mohar and S. Poljak, Eigenvalues and the max-cut problem, Czechoslovak Math.\ J. 40 (1990), 343--352; 10.21136/CMJ.1990.102386.DOI
  30. M. Morgenstern, Existence and explicit constructions of q+1q+1 regular Ramanujan graphs for every prime power qq, J. Combin.\ Theory Ser. B 62 (1994), 44--62; 10.1006/jctb.1994.1054.DOI
  31. M. B. Paterson and D. R. Stinson, Circular external difference families, graceful labellings and cyclotomy, Discrete Math. 347 (2024), 114103; 10.1016/j.disc.2024.114103.DOI
  32. S. Poljak and Z. Tuza, Maximum bipartite subgraphs of Kneser graphs, Graphs Combin. 3 (1987), 191--199; 10.1007/BF01788540.DOI
  33. L. Rédei and A. Rényi, On the representation of the numbers 11, 22, , NN by means of differences (in Russian), Mat.\ Sbornik 24(66) (1949), 385--389.
  34. A. Rosa, On certain valuations of the vertices of a graph, in Theory of Graphs (Internat.\ Symposium, Rome, July 1966), Gordon and Breach, New York and Dunod, Paris, 1967, 349--355.
  35. A. Rosa, O cyklických rozkladoch kompletného grafu , Kandidátska dizertačná práca, ČSAV, Bratislava, 1965.
  36. W. Rudin, Fourier Analysis on Groups , Interscience, 1962.
  37. J. B. Shearer, Improved LP lower bounds for difference triangle sets, Electron.\ J. Combin. 6 (1999), #R31; https://www.combinatorics.org/ojs/index.php/eljc/article/view/v6i1r31.link
  38. T. Skolem, On certain distributions of integers in pairs with given differences, Math.\ Scand. 5 (1957), 57--68; 10.7146/math.scand.a-10490.DOI

Version history

  1. v1Submitted by Boon Suan HoInitial depositSupersededOct 17, 2026
  2. v2Submitted by Boon Suan HoSubmitted as a new versionCurrentOct 18, 2026