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.