A tree with n vertices is called graceful if its vertices can be labelled with…

Concept: A tree with n vertices is graceful if we can assign the labels 1, 2, ..., n to its n vertices (each label used once) so that its n−1 edges receive edge-differences (the absolute difference between an edge's two endpoint labels) that are all distinct -- since a tree has exactly n−1 edges, this forces the differences to be precisely 1, 2, ..., n−1, each appearing once. A standard way to build such a labelling on a straight path is to alternate between the smallest and largest still-unused numbers while walking along the path; a tree that is a path with one short extra branch (a "caterpillar" tree) can usually still be labelled this way with a small adjustment near the branch.

Applying it to tree (a) -- the 4-vertex path v1–v2–v3–v4, drawn left to right in the figure:

1. Assign v1 the smallest available number: v1 = 1.

2. Assign v2 the largest available number: v2 = 4.

3. Assign v3 the next-smallest available number: v3 = 2.

4. Only one number remains, so v4 gets it: v4 = 3.

5. Edge differences: |v1−v2| = |1−4| = 3, |v2−v3| = |4−2| = 2, |v3−v4| = |2−3| = 1.

These differences are {3, 2, 1} -- exactly the numbers 1 to 3 (n−1 = 3), each once -- so tree (a) is graceful. This is exactly why v4 ends up labelled 3: it is simply whichever number is left over once the alternating rule has already used 1, 4 and 2 for v1, v2 and v3.

Applying it to tree (b) -- main chain v1–v2–v4–v5 with a pendant v3 attached at v2 (as drawn: v1, v2 and v5 sit on the upper line, v4 sits on the chain between v2 and v5, and v3 hangs below v2):

1. v1 = 2

2. v2 = 5

3. pendant v3 = 4

4. v4 = 1

5. v5 = 3

6. Edge differences: |v1−v2| = |2−5| = 3; |v2−v3| = |5−4| = 1 (the pendant edge); |v2−v4| = |5−1| = 4; |v4−v5| = |1−3| = 2.

These differences are {3, 1, 4, 2} -- exactly 1 to 4 (n−1 = 4) -- so tree (b) is graceful too; here the branch at v2 is handled by giving the pendant v3 the next-largest remaining number instead of following the plain alternating order.

Applying it to tree (c) -- main chain v1–v2–v3–v5–v6 with a pendant v4 attached at the middle vertex v3 (as drawn along the main row, with v4 hanging below v3):

1. v1 = 1

2. v2 = 6

3. v3 (centre) = 2

4. pendant v4 = 5

5. v5 = 4

6. v6 = 3

7. Edge differences: |v1−v2| = 5; |v2−v3| = 4; |v3−v4| = 3 (the pendant edge); |v3−v5| = 2; |v5−v6| = 1.

These differences are {5, 4, 3, 2, 1} -- exactly 1 to 5 (n−1 = 5) -- so tree (c) is graceful as well.

Cross-check: for any graceful labelling the edge-differences must be exactly 1, 2, ..., n−1, so their sum must equal (n−1)n/2. Tree (a): 3+2+1 = 6 = (3·4)/2. Tree (b): 3+1+4+2 = 10 = (4·5)/2. Tree (c): 5+4+3+2+1 = 15 = (5·6)/2. All three sums match, confirming none of the computed differences repeats or falls outside the required range.

A tree not being a straight line -- that is, having a vertex with more than two neighbours, like v2 in tree (b) or v3 in tree (c) -- does not by itself prevent a graceful labelling; it only means the plain alternating rule needs a small adjustment at the branch, as shown above.

Since each of the three pictured trees has an explicit 1-to-n labelling whose edge differences are all distinct, all three pictured trees are graceful.