Graceful Graph Moves

1. The extreme sprout
2. Proof: All paths are graceful.
3. Proof: All caterpillars are graceful.
4. The leaf pair and midpoint transfers
5. Proof: All double stars are graceful.
6. Banana trees!
7. The label-sum transfer
8. References

In 2020, I was slowly reading Douglas West’s Introduction to Graph Theory and somehow became very interested in the Graceful Tree Conjecture (GTC), which triggered me to write this post. There’s nothing novel in that write-up; it was mostly a notes-to-self, and a place for me to play with nice diagrams. That’s what this post is too.

I set aside graph theory after a few months, picked it back up for Arcol (see here), and returned to it recently. My recent interest is due to frontier models becoming decent at math. Over the past few weeks I’ve had many fun, mathematically lively conversations with GPT-5.5 about the GTC and related matters. One thing I had forgotten is that, if true, the GTC implies Ringel’s tree-packing conjecture, which is itself a fascinating conjecture that is useful in combinatorial design theory.

GPT-5.5 taught me about different families of trees that have been proven to be graceful. Here are three examples: paths, caterpillars, and any tree with a diameter of $5$ or less. Interestingly spiders and lobsters have not been settled at the time that I write this, but various subfamilies have been proven to be graceful.

The diameter of a tree is the largest distance, measured in edges, between any two vertices. A leaf is a vertex of degree $1$. A path is a tree whose vertices can be arranged in a single chain, so it has no branching. A caterpillar is a tree for which one can choose a path, called the spine, so that every vertex not on the spine is a leaf adjacent to a spine vertex. Those off-spine leaves are called legs. This convention matters: a spine endpoint can itself be a leaf of the whole tree, but it is not a leg for the construction that we’ll be using later. Note that our definition allows spine vertices to have more than one incident leg.

Using a constructive proof is an easy way to show that one of the above families is graceful. These kinds of proofs rely on transformations that promise to preserve gracefulness. I call them “moves” because some of them remind me a bit of Reidemeister moves from knot theory. Also “moves” makes it feel like a game.

Stars are almost too easy for this list, but they are worth keeping in mind. The star $K_{1,n}$ is graceful: label its center $0$ and label its $n$ leaves $1,2,\ldots,n$. The edge labels are then exactly $1,2,\ldots,n$.

The extreme sprout

Here’s our first move. It’s especially useful for paths and caterpillars, as you’ll see.

Note that in both cases described by the move, the old edge labels remain as-is.

Proof: All paths are graceful.

Let’s use the extreme sprout move to prove that all paths permit a graceful labeling. We’ll induct on $q$, the number of edges in the path. In fact, the induction proves a slightly stronger statement: for every $q \ge 0$, there is a graceful labeling of $P_q$ with an attachment point at one end of the path, labeled $0$ when $q$ is even and labeled $q$ when $q$ is odd.

For the base case, $P_0$ is a single vertex labeled $0$. For the inductive step, assume the stronger statement holds for $P_q$. Apply the extreme sprout move at the attachment point. If that point is labeled $0$, the move gives the new leaf label $q + 1$. If that point is labeled $q$, the move gives the new leaf label $0$. In either case, the new leaf becomes the attachment point of the longer path, so the parity condition flips exactly as it should. Thus the stronger statement holds for $P_{q+1}$, and therefore every path is graceful.

Proof: All caterpillars are graceful.

To prove that all caterpillars are graceful, choose a left-to-right orientation of the spine and write its vertices as $v_0, v_1, v_2, \ldots$. Let $a_i$ be the number of legs that need to be attached to $v_i$. We will grow the caterpillar from left to right. At each spine vertex, we first attach its legs, then move on by attaching the next spine vertex.

Now begin with the one-vertex graph consisting only of $v_0$, labeled $0$. At any moment, the rightmost spine vertex is an extreme label. More precisely, after reaching $v_i$, that vertex has label $0$ when $i$ is even and has the current maximum label when $i$ is odd.

At $v_i$, create every new neighbor by applying the extreme sprout move: first the $a_i$ legs, and then, unless $v_i$ is the last spine vertex, $v_{i+1}$. If $i$ is even, then $v_i$ is labeled $0$, so the move assigns the new neighbor the current maximum label. Thus the next spine vertex, if one is created, becomes the maximum-labeled endpoint. If $i$ is odd, then $v_i$ has the current maximum label, so the move assigns the new neighbor label $0$. Thus the next spine vertex, if one is created, becomes the $0$-labeled endpoint.

At the last spine vertex, this rule attaches only the remaining legs. At that point every spine edge and every leg of the target caterpillar has been added. Since each individual sprout preserves gracefulness, every intermediate graph is graceful, and the final caterpillar is graceful.

The leaf pair and midpoint transfers

Next we’ll use these transfer rules to prove that an interesting family of trees is graceful.

Proof: All double stars are graceful.

A double star is a tree with two adjacent vertices $x$ and $y$, called the centers, such that every other vertex is a leaf attached to one of the centers. Write $D_{a,b}$ for the double star with $a$ leaves attached to $x$ and $b$ leaves attached to $y$, in addition to the center edge $xy$. Thus $D_{a,b}$ has $a+b+1$ edges and $a+b+2$ vertices. Pay attention to the parity of $b$, the number of leaves attached to $y$; it’s an important factor in the proof.

By the definition above, every double star is already a caterpillar: take the center edge $xy$ as the spine, and every other vertex is a leg. So this family is already covered by the caterpillar proof. I still want to give a separate proof because it shows off different move types that come in handy for more complicated families.

Let’s set aside the corner case where one of the stars has no leaves, because then we just have a single star. So assume $a,b \ge 1$, and let $q=a+b+1$. Start with the star $K_{1,q}$, centered at $x$ and gracefully labeled by $$f(x)=0,\qquad f(\text{leaves})=\{1,2,\ldots,q\}.$$ This star has one more leaf than the final number of leaves because one of its leaves will become the second center $y$.

Choose which leaf will become $y$ by finding the vertex with the following label: $$f(y)=c= \begin{cases} b+1, & b \text{ is odd},\\ b+2, & b \text{ is even}. \end{cases}$$ In both cases, we can choose exactly $b$ leaf labels below $c$ and move them from $x$ to $y$ using only leaf pair transfers and leaf midpoint transfers. The allowed sum for every transfer is $$f(x)+f(y)=c,$$ so we only need leaf labels that are paired around $c$, with at most one midpoint label.

If $b$ is odd: then $c=b+1$. Move the leaves labeled $1,2,\ldots,b$: pair $1$ with $b$, pair $2$ with $b-1$, and so on, and use one midpoint transfer for the leaf labeled $(b+1)/2$.

If $b$ is even: then $c=b+2$. Move all leaves labeled $1,2,\ldots,b+1$ except the midpoint leaf; these labels split completely into complementary pairs whose sums are $b+2$.

Each move preserves label sums, so after all the moves the labeling in the double-star is still graceful.

Banana trees!

By carefully extending the double-star proof it’s possible to show that another delicious family of trees is graceful. Sethuraman and Jesintha proved this in 2009. If you eyeball the example figure below, you can see how it’s a bit like a generalized multi-star.

For $r\ge 1$ and nonnegative integers $a_1,\ldots,a_r$, the banana tree $B(a_1,\ldots,a_r)$ has vertices $$v_0,\quad p_1,\ldots,p_r,\quad w_1,\ldots,w_r,\quad u_{j,k}\ (1\le j\le r,\ 1\le k\le a_j),$$ and edges $$v_0p_j,\quad p_jw_j,\quad w_ju_{j,k}.$$ So the root $v_0$ is attached to one leaf of each star, and the $j$th star has center $w_j$ and $a_j$ remaining leaves.

For the animated proof we’ll forgo the usual step-by-step description and just play it through in a loop for fun:

As you can imagine, the bookkeeping involved in the Sethuraman-Jesintha proof is a bit mind-bending! See their paper for details.

The label-sum transfer

The last move I want to describe generalizes the leaf transfer rules. It lets you transfer one or two entire subgraphs from one place to another.

This move was used in the Hrnčiar-Haviar proof that every tree with diameter $5$ is graceful. There’s quite a bit of machinery in that proof so it’s a bit out of scope for this post.

References

• A. Rosa, “On certain valuations of the vertices of a graph,” Theory of Graphs, 1967, 349-355.
• S. W. Golomb, “How to number a graph,” in Graph Theory and Computing, 1972, 23-37.
• J. A. Gallian, “Graph Labeling,” Electron. J. Combin., DS6.
• R. Montgomery, A. Pokrovskiy, B. Sudakov, “A proof of Ringel’s conjecture,” Geom. Funct. Anal. 31 (2021), 663-720.
• P. Hrnčiar, A. Haviar, “All trees of diameter five are graceful,” Discrete Math. 233 (2001), 133-150.
• G. Sethuraman, J. Jeba Jesintha, “All banana trees are graceful,” Adv. Appl. Discrete Math. 4(1) (2009), 53-64.

graceful-moves-20260530-a.md / graceful-moves-20260530-a.md.ots

graceful-moves-20260530-b.md / graceful-moves-20260530-b.md.ots