Labeling binary trees so that adjacent vertices differ by a power of two

Question

Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the numbers from $0$ to $n-1$, each occurring exactly once, the root having label zero, and so that the label of a vertex is always equal to the label of its parent plus some power of two?

Equivalently:

Let $G$ be the oriented graph whose vertices are the integers between $0$ and $n-1$, with an edge pointing from $i$ to $j$ whenever $j-i$ is a power of two. Is it true that $G$ is "universal" for spanning binary trees, in the sense that every binary tree $T$ on $n$ nodes, oriented away from its root, is a subgraph of $G$?

(This question was asked to me, in slightly different terms, by a bioinformatician friend. At first I didn't believe it because it seems so unreasonable, but experimental data suggests that it might be true, and I have no idea why.)

I emphasize that what makes the question difficult is that the labeling has to be bijective (or, in the second formulation, $T$ is a spanning tree for $G$).

The closest I could find in the literature is the paper "On Universal Graphs for Spanning Trees" by Chung & Graham, J. London Math. Soc. 27 (1983) 203–211, mentioned in an answer to this related question, but I don't see how to apply it or adapt its technique to this particular graph $G$. The only thing I can see is that, at least, $G$ has a sensible number of edges (viz. of the order of $n\log n$).

Answer 1

I have had a chance to edit my previous answer which was deleted because it was fatally flawed. This argument does not answer the question, but says something about how a minimal counterexample would have to look. I will bring the post back because I think this is a very nice question and perhaps these observations can either be extended to a proof or aid in the search for a counterexample. The first claim is essentially my previously deleted answer. The second claim is along the line of Gerhard Paseman's observations.

If $T$ is a tree on $n$ vertices we will write $|T| = n$. For a rooted binary tree $T$ as in the question let $L$ and $R$ denote the rooted binary trees making up the branches to the left and right of the root node respectively. Assume $T$ is a counter example with $|T|=n$ minimal.

Claim: $|L| \neq |R|$.

Assume $|L| = |R|$. Since $T$ is a minimal counterexample we may give a labeling to $L$ and $R$ satisfying our property. Now multiply all labels of $L$ by $2$ and then add $1$ to all labels. Also multiply all labels of $R$ by $2$ and then add $2$ to all labels. Giving to root node a label of $0$ gives a desired labeling to $T$. Notice scaling by $2$ and shifting preserves the fact that all differences are a power of $2$. Also the root node of $T$ labeled $0$ differs from its children by $1$ and $2$. Because $|L| = |R|$ the labeling will use exactly $\{0,1,\dots, n-1\}$. On $L$ the non-zero odd integers will be used, and the non-zero even integers are used on $R$.

Claim: Neither $|L|$ nor $|R|$ are of the form $2^k - 1$.

WLOG assume $|L| = 2^k - 1$. Since $T$ is a minimal counterexample we may give a labeling to $L$ and $R$ satisfying our property. Now add $1$ to all the labels of $L$ and $2^k$ to all the labels of $R$. Then giving to root node of $T$ the label $0$ satisfies our property, with $L$ labeled with $\{1,2,\dots,2^k - 1\}$ and $R$ labels starting at $2^k$.

Answer 2

I can get close, but someone else may have to finish it.

John Machacek had some interesting points. Adding the same value to each label preserves the difference property, as does multiplying by a power of two. Also, multiplying by -1 preserves this property, and from this one concludes reversing the order (replacing j by n-j-1) also does.

(Right now, desired means adjacent vertex labels differ by a power of two, that 0 through n-1 is used as in the problem, and not that the root has zero.) Suppose we have the desired labelling for a tree with m nodes and one with n nodes. Suppose further that we can find labelling which assigns 0 to each root. Then we get a desired labelling on n+m+1 vertices by assigning n to the new root, n-1 to the old root of the n tree, n+1 to the m tree, and then modifying the labels of the n and m trees in a predictable fashion. We can do similarly with the new root being labelled with m.

We could complete the proof if we could take this labelling and tweak it so that zero moved to the top. Otherwise we have to find a new way to label the new root, or build such a labelling of the n+m+1 tree so that it can have a root labelled with zero.

Note that 0 can't be transported to any node of a binary tree with such a labelling, as experimenting with n=4 shows.

Gerhard "Thumb Is Not Green Enough" Paseman, 2018.07.04.