Is my Graph Graceful?

Question

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

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.

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.

Task

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

This is code-golf so the objective is to minimize your byte count.

Test Cases

Here graphs are represented as an array of edges:

3 nodes:

[(0,1),(0,2),(1,2)]

True

Labeling:

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

---

5 nodes:

[(0,1),(0,4),(1,2),(2,3),(3,4)]

False

---

5 nodes:

[(0,1),(1,2),(2,3),(3,4)]

True

Labeling:

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

---

9 nodes

[(0,1),(1,2),(1,7),(1,8),(2,3),(2,6),(3,4),(4,5)]

True

Labeling:

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

[(0,1),(0,2),(1,2),(1,3),(1,4),(3,4)]

False

Answer 1

Jelly, 12 bytes

FSŒ!ị@€ḅ-AċJ

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.

Answer 2

Mathematica, 121 116 bytes

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

Cases[Range[1+Tr[n=Range@Length[e=EdgeList@#]]]~Tuples~VertexCount@#,w_/;Sort[Abs[#-#2]&@@w[[List@@#]]&/@e]==n]!={}&

Explanation

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. 

Answer 3

Python3, 449 bytes

R=range
def f(g):
 q=[(v:={**{i:-1 for j in g for i in j},0:0},[],{*v}-{0})]
 while q:
  m,e,n=q.pop(0)
  if not n:
   if all(i in e for i in R(1,len(g)+1)):return m
   continue
  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})] 
    break

Try it online!