# Graceful Graph Moves
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](../graceful). 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](https://blog.arcol.io/pen-tool)), 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.
::::: {.aside}
Quanta Magazine has a nice write-up about the Ringel Conjecture [here][quanta].
However it's a bit slippery to say that the problem has been solved: what has
been proven is the large-tree case. That's a big deal, but the original
conjecture is still open (as I write this anyway).
:::::
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$.
Two graceful labelings of $K_{1,5}$. The right labeling is the complement of the left one, so the vertex labels invert while the edge labels stay the same.
## [The extreme sprout](#the-extreme-sprout)
Here's our first move. It's especially useful for paths and caterpillars, as
you'll see.
::::: {.statement2}
::: {.statement2-title}
The extreme sprout
:::
::: {.statement2-content}
Suppose $G$ is a gracefully labeled graph with $q$ edges.
- If a vertex $x$ is labeled $0$, attach a new leaf $y$ to $x$ and label it
with $q + 1$.
- If a vertex $x$ is labeled $q$, first add $1$ to every old vertex label,
then attach a new leaf $y$ to $x$ and label $y$ with $0$.
Either way, $x$ is the **attachment point** of the move.
:::
:::::
Note that in both cases described by the move, the old edge labels remain
as-is.
### [Proof: All paths are graceful.](#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.](#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](#the-leaf-pair-and-midpoint-transfers)
::::: {.statement2}
::: {.statement2-title}
The leaf pair transfer
:::
::: {.statement2-content}
Suppose $T$ is a gracefully labeled tree, and suppose $u$ has two attached
leaves that we want to move to another vertex $v$. A **leaf pair transfer**
from $u$ to $v$ deletes the old edges from $u$ to those two leaves and
replaces them with edges from $v$ to the same leaves. No vertex labels are
changed. If the moved leaves have labels $s$ and $t$, the transfer is allowed
when
$$
s+t=f(u)+f(v).
$$
:::
:::::
::::: {.statement2}
::: {.statement2-title}
The leaf midpoint transfer
:::
::: {.statement2-content}
Suppose $T$ is a gracefully labeled tree, and suppose $u$ has one attached
leaf that we want to move to another vertex $v$. A **leaf midpoint transfer**
from $u$ to $v$ moves exactly one leaf from $u$
to $v$: it deletes the old edge from $u$ to that leaf and replaces it with an
edge from $v$ to the same leaf. No vertex labels are changed. If the moved
leaf has label $s$, the transfer is allowed when
$$
2s=f(u)+f(v).
$$
:::
:::::
Leaf pair and midpoint transfers. Blue leaves move; gray leaves stay put. Rows with more than one moved group are sequences of atomic moves.
Next we'll use these transfer rules to prove that an interesting family of trees
is graceful.
### [Proof: All double stars are 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.
An example double star $D_{4,3}$. The two center vertices are joined by the center edge, with four leaves attached on the left and three leaves attached on the right.
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!](#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-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.
::::: {.statement2}
::: {.statement2-title}
The label-sum transfer
:::
::: {.statement2-content}
Suppose $T$ is a gracefully labeled tree. Consider one or two branches attached
to $u$, where a branch means the whole component hanging off $u$ through its
root. Call the roots $u_1$ and, in the two-branch case, $u_2$. Let $v$ be
outside those branches. A **label-sum transfer** from $u$ to $v$ moves the
branch or branches by replacing the attachment edges from $u$ with attachment
edges from $v$. No vertex labels are changed.
For two branches, the required condition is
$$
f(u_1) + f(u_2) = f(u) + f(v)
$$
For a single branch rooted at $u_1$, the required condition is the midpoint
case
$$
2 f(u_1) = f(u) + f(v)
$$
:::
:::::
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](#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) / [graceful-moves-20260530-a.md.ots](graceful-moves-20260530-a.md.ots)
[quanta]: https://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/
[Reidemeister moves]: https://mathworld.wolfram.com/ReidemeisterMoves.html
