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 2 / 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 and in a revision of version 1, from which some passages of version 2 are adapted. Claude also ran the literature searches, independent reviews of the draft, and computer searches (Python, OR-Tools CP-SAT, C). The finite and numerical claims of the paper are checked by Python scripts at https://github.com/boonsuan/tools, written by Claude, in exact rational arithmetic wherever a proof uses them. 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. C. Bordenave, A new proof of Friedman's second eigenvalue theorem and its extension to random lifts, Ann.\ Sci.\ Éc.\ Norm.\ Supér. (4) 53 (2020), 1393--1439; 10.24033/asens.2450.DOI
  10. 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
Show all 55 referencesShow fewer references
  1. A. E. Brouwer and W. H. Haemers, Spectra of Graphs , Springer, 2012; 10.1007/978-1-4614-1939-6.DOI
  2. W. G. Brown, On graphs that do not contain a Thomsen graph, Canad.\ Math.\ Bull. 9 (1966), 281--285; 10.4153/CMB-1966-036-2.DOI
  3. N. G. de Bruijn, On number systems, Nieuw Arch.\ Wisk. (3) 4 (1956), 15--17.
  4. A. Burgess, F. Merola and T. Traetta, On circular external difference families, preprint, 2509.02731 , 2025.
  5. 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
  6. 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
  7. 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
  8. 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
  9. C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math.\ Programming 62 (1993), 557--574; 10.1007/BF01585184.DOI
  10. S. Dore-Hall, Gracefulness of mK4mK_4-snakes for m=3,4,5m=3,4,5, abstract, 28th Coast Combinatorics Conference, University of Victoria, March 2018, p. 3; https://webdocs.cs.ualberta.ca/~hayward/papers/CCC2018Program.pdf.link
  11. P. Erdős and A. Rényi, On a problem in the theory of graphs, Publ.\ Math.\ Inst.\ Hungar.\ Acad.\ Sci. 7 (1962), 623--641.
  12. P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math.\ Soc. 16 (1941), 212--215; 10.1112/jlms/s1-16.4.212.DOI
  13. M. Ferrara, Y. Kohayakawa and V. Rödl, Distance graphs on the integers, Combin.\ Probab.\ Comput. 14 (2005), 107--131; 10.1017/S0963548304006637.DOI
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. B. S. Ho, answer to ``Do the windmills K5(3)K_5^{(3)} and K5(4)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
  20. 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
  21. D. E. Knuth, Coups de grâceful graphs, unpublished note, 2020, revised 2026, https://cs.stanford.edu/~knuth/papers/coups.pdf.link
  22. D. E. Knuth, The Art of Computer Programming , Volume 4, Fascicle 7: Constraint Satisfaction , Addison-Wesley, 2025.
  23. 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.
  24. 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.
  25. 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
  26. J.-B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear 00--11 programs, SIAM J. Optim. 12 (2002), 756--769; 10.1137/S1052623400380079.DOI
  27. M. Laurent, A comparison of the Sherali--Adams, Lovász--Schrijver, and Lasserre relaxations for 00--11 programming, Math. Oper. Res. 28 (2003), 470--496; 10.1287/moor.28.3.470.16391.DOI
  28. 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
  29. B. Lindström, An inequality for B2B_2-sequences, J. Combin.\ Theory 6 (1969), 211--212; 10.1016/S0021-9800(69)80124-9.DOI
  30. 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
  31. A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261--277; 10.1007/BF02126799.DOI
  32. C. Ma and X. Yi, An almost-covering threshold for Golomb-ruler difference packings, preprint, 2608.13739 , 2026.
  33. R. Mathon, Constructions for cyclic Steiner 22-designs, RIMS Kôkyûroku 607 (1987), 22--32.
  34. B. Mohar and S. Poljak, Eigenvalues and the max-cut problem, Czechoslovak Math.\ J. 40 (1990), 343--352; 10.21136/CMJ.1990.102386.DOI
  35. 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
  36. nickgard, answer to ``Is Paley-13 a graceful graph?'', Mathematics Stack Exchange, June 2019; https://math.stackexchange.com/q/3250051.link
  37. 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
  38. S. Poljak and Z. Tuza, Maximum bipartite subgraphs of Kneser graphs, Graphs Combin. 3 (1987), 191--199; 10.1007/BF01788540.DOI
  39. 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.
  40. 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.
  41. A. Rosa, O cyklických rozkladoch kompletného grafu , Kandidátska dizertačná práca, ČSAV, Bratislava, 1965; scans at https://www-cs-faculty.stanford.edu/~knuth/A.Rosa-thesis-page0-20.pdf and three further files there.link
  42. W. Rudin, Fourier Analysis on Groups , Interscience, 1962.
  43. 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
  44. D. A. Sheppard, The factorial representation of balanced labelled graphs, Discrete Math. 15 (1976), 379--388; 10.1016/0012-365X(76)90051-0.DOI
  45. 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