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!

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. 

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.