## A Problem on Trees and Cubes

by
Tomás Feder

Let T be a tree with vertices of degrees 1,2,3 that has 2 to the power n
vertices on each side of the bipartition. It is conjectured that T is
a subgraph of a hypercube of dimension n+1.

We can show that if T is a tree with vertices of degrees 1,3 that has
a,b vertices on the two sides of the bipartition respectively, then T
has a subtree T' containing any given leaf x, such that the leafs of T'
are leafs of T, and T' has (a+1)/2, (b+1)/2 vertices on the two sides
of the bipartition respectively. The proof places x at the root and
shows that any leaf y at the bottom level or one or two levels higher can
be avoided in T', except for three specific cases of T, one with the
leaf y adjacent to x, and two with the leaf y at distance three from x.
The proof is by induction, places x at the root, and decomposes T into
subtrees rooted at vertices at distance one or two from x, while omitting
vertices at the bottom one or two levels if necessary for the induction,
where the omitted vertices are descendants of chosen vertices y in the
subtree. The three specific cases of T that do not work for the induction
as base cases, but for which the theorem without chosen y works as well,
are T1=xy, T2=xa,ab,ac,bd,by,ce,cf,dg,dh, and T3=T2,gi,gj,hk,hl.