# Graceful Graphs

## Problem Description

A graph (V,E) is called a graceful graph if its vertices V can be labelled with distinct integers from 0 to |E| such that, when each edge is labelled with the absolute difference between its vertex labels, the resulting edge labels are all distinct. The task is to determine the existence of a graceful labelling of a graph.

## Predicates

**Input**:`edge/2`**Output**:`value/2`

## Input format

The edges of the graph are provided by instances of the predicate `edge/2`.

## Output format

If a graceful labelling exists, a witness containing vertex labels encoded in the predicate `value/2` has to be provided. `value(X,I)` means the vertex X is labelled with the unsigned integer I.

## Example(s)

The example encodes a clique with 3 nodes:

edge(a,b). edge(b,c). edge(c,a).

It is graceful. An assignment of the values 0, 1, and 3 to the nodes provides a graceful labelling.

Thus, the output of the solver should look like:

value(a,0). value(b,1). value(c,3).

Other graceful labellings are also possible.

Additional sample instances: download

## Problem Peculiarities

**Type**: Search **Competition**: Both **Complexity**: NP

## Notes and Updates

- Feb 2nd, 2013 - Problem Description updated

## Author(s)

- Author: Christian Drescher
- Affiliation: NICTA, University of New South Wales, Australia