A Graceful Graph is a type of Simple Graph. Graceful graphs are special because there is a way to label all their nodes with positive integers so that when the edges are also labeled with the differences of the nodes they connect, no two edges have the same label and every label up to the number of edges is used.

Worked Out Example

Here is a Simple graph that we suspect is a Graceful graph

Simple Graph

Let us try the following labeling:


Note we are permitted to skip integers in our node labeling. Now we label every edge with the positive difference between the nodes it connects. For increased visibility I have labeled these in red.

Doubly labeled

Each edge has a unique number and no number between between 1 and 7 (the number of edges we have) is left out. Thus our graph is graceful.


Given a graph, via any reasonable method of input, output a truthy value if it is graceful and a falsy value otherwise.

This is so the objective is to minimize your byte count.

Test Cases

Here graphs are represented as an array of edges:

3 nodes:




Node 0 -> 0
Node 1 -> 2
Node 2 -> 3

5 nodes:



5 nodes:




Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10

9 nodes




Node 0 -> 0
Node 1 -> 1
Node 2 -> 3
Node 3 -> 6
Node 4 -> 10
Node 5 -> 15
Node 6 -> 11
Node 7 -> 7
Node 8 -> 8

5 nodes


  • \$\begingroup\$ I think algorithms to check gracefulness are only known for certain classes of graphs (e.g. trees) \$\endgroup\$
    – user61980
    Feb 17, 2017 at 2:56
  • 2
    \$\begingroup\$ @ngenisis It can certainly be brute forced. There are more efficient algorithms for certain classes but you can use restraints on the edge sizes to create a maximum node label difference. \$\endgroup\$
    – Wheat Wizard
    Feb 17, 2017 at 3:00
  • \$\begingroup\$ [(0,1),(1,2),(2,3),(3,4)] is probably a noteworthy edge case. \$\endgroup\$
    – Dennis
    Feb 17, 2017 at 4:03
  • \$\begingroup\$ Unless I'm missing something, graphs of the form {(k-1,k) : 0 < k < n} require the highest labels of all graphs with the same number of nodes. \$\endgroup\$
    – Dennis
    Feb 17, 2017 at 4:16
  • \$\begingroup\$ @Dennis Oh yes. That is certainly true they should require n(n+1)/2 as their highest label. I have added your test case. \$\endgroup\$
    – Wheat Wizard
    Feb 17, 2017 at 4:19

3 Answers 3


Jelly, 12 bytes


Takes an array of edges as 1-indexed node pairs.

Try it online! (Horrendously inefficient. Don't bother with the actual test cases.)

How it works

FSŒ!ị@€ḅ-AċJ  Main link. Argument: A (array of pairs)

FS            Flatten and sum, yielding s. This is an upper bound for the labels
              a graceful labeling (if one exists) would require.
  Œ!          Take all permutations of [1, ..., s].
      €       For each permutation P:
    ị@          Replace each integer in A with the element of P at that index.
       ḅ-     Convert all pairs from base -1 to integer, mapping (a,b) to b-a.
         A    Take absolute values.
           J  Yield the indices of A, i.e., [1, ..., len(A)].
          ċ   Count the occurrences of [1, ..., len(A)] in the result to the left.
  • 3
    \$\begingroup\$ ḅ- is one of my favorite Jelly tricks :-) \$\endgroup\$ Feb 17, 2017 at 15:07

Mathematica, 121 116 bytes

Edit: Saved 5 bytes thanks to JungHwan Min and Martin Ender



enter image description here

Pure function which takes a Mathematica Graph object with vertices {1, 2, ..., k} for some nonnegative integer k. In the worst case, we will only need vertex labels ranging from 1 to 1 + (1 + 2 + ... EdgeCount@#). Since it saves us some bytes later, we will let e be the list of edges and n be the list {1, 2, ..., EdgeCount@#}, so the vertex weights will be drawn from Range[1+Tr[n=Range@Length[e=EdgeList@#]]]. We generate a list of all Tuples of length VertexCount@#, then we choose the Cases which give graceful labelings and check to see that the result is Unequal to the empty list {}. Gracefulness of the list of vertex weights w is checked by Mapping the function Abs[#-#2]&@@w[[List@@#]]& over the list of edges e, Sorting the result, and checking whether the result is Equal to n. Here is a breakdown of that function:

               List@@#     Replace the Head of the edge with List; i.e., UndirectedEdge[a,b] becomes {a,b}.
            w[[       ]]&  Select the corresponding vertex weights from the list w.
          @@               Replace the Head of that expression (List) with the function
Abs[#-#2]&                   which returns the absolute difference between its first two arguments.
                           This effectively passes the vertex weights into the absolute difference function. 
  • 1
    \$\begingroup\$ save a byte by messing with some precedence: VertexCount[#]->VertexCount@# \$\endgroup\$ Feb 17, 2017 at 4:45
  • 1
    \$\begingroup\$ Btw, the Tr trick for Length no longer saves bytes if you need to add parentheses. Length[e=EdgeList@#] is the same length. But it's shorter to avoid that altogether and rewrite the triangular number there as Tr@Range@EdgeCount@# (and then replace e at the end with EdgeList@#. Second, the function operator rarely saves bytes, in this case I think it's shorter to use Cases instead of Select and then w_/; instead of w. \$\endgroup\$ Feb 17, 2017 at 8:49

Python3, 449 bytes

def f(g):
 q=[(v:={**{i:-1 for j in g for i in j},0:0},[],{*v}-{0})]
 while q:
  if not n:
   if all(i in e for i in R(1,len(g)+1)):return m
  for i in n:
   if(k:=[N for j in g if i in j and m[(N:=j[j[1]!=i])]!=-1]):
    y=[m[N]for N in k]
    for o in{*R(min(y)+1,max(y)+len(g)+1)}-{*m.values()}:
     E=[abs(Y-o)for Y in y]
     if all(U not in e and U<=len(g)for U in E):q+=[({**m,i:o},e+E,n-{i})] 

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.