Generating graceful unicyclic graphs from a given forest

NEW

Problem: Reconstructed statement: every finite simple connected unicyclic graph $U$ can be embedded as a subgraph of a graceful unicyclic graph. Here a graph with $q$ edges is graceful if its vertices admit distinct labels in $\{0,\dots,q\}$ such that the edge-differences are exactly $\{1,\dots,q\}$. “Embed” is interpreted as subgraph; the construction below gives an induced embedding on the original vertex set.

Result: The statement is true.

Let $U$ have $n$ vertices and $n$ edges. Choose a root $r$, a spanning tree $T$ rooted at $r$, and order the non-root vertices $v_1,\dots,v_{n-1}$ so that parents precede children. Define

Let $Q=4^{n-2}$. Then all pairwise differences among labels of vertices of $U$ are distinct: differences $4^a$ from $0$ are never equal to differences $4^a-4^b$, and equality

forces $b=d$ by 2-adic valuation and then $a=c$. Hence the edge-differences of $U$ are distinct.

Let $P=\{f(v):v\neq r\}$, and let $D$ be the set of edge-differences already occurring on $U$. A power $f(v)\in P$ lies in $D$ exactly when $rv\in E(U)$, since nonzero differences of two powers of $4$ are not powers of $4$.

For every vertex $v\neq r$ with $rv\notin E(U)$, let $p(v)$ be its parent in $T$. Then $f(p(v))>f(v)$, and

Add a new leaf $x_v$ adjacent to $p(v)$, labeled $f(x_v)=\ell_v$. This new edge has difference

Thus every missing edge-difference belonging to $P\setminus D$ is supplied.

Finally, for every integer

add a new leaf $y_d$ adjacent to $r$, labeled $f(y_d)=d$. Its edge-difference is $d$.

All labels are distinct. The edge-differences are exactly:

• $D$, from the original graph $U$;
• $P\setminus D$, from the special leaves $x_v$;
• $\{1,\dots,Q\}\setminus(P\cup D)$, from the root leaves $y_d$.

Hence the edge-differences are precisely $\{1,\dots,Q\}$.

Counting shows the resulting graph has exactly $Q$ edges and $Q$ vertices, so the labeling is graceful with $Q$ edges. Since only leaves were attached to $U$, the graph remains connected and unicyclic, and $U$ is an induced subgraph.

Thus every finite simple unicyclic graph embeds in a graceful unicyclic graph.

Citation: No prior resolution is used here; this is a direct construction.