MATH.4:5.2 - Strengthen the construction to color a tree

Consider finite binary trees formed as Leaf or Branch(left,right). A leaf is one vertex. A branch adds a new root with edges to the roots of its two constituent trees. The constituent vertices occur separately in the constructed tree.

The required output colors each vertex 0 or 1 so that each edge joins different colors. Suppose a first attempt always colors a root zero. At a new branch, using those subtree results unchanged would give edges from zero to zero.

Generalize the construction: Color(t,c) takes a tree and a required root color c∈{0,1}. Its result must have root color c and different colors across every edge.

• For Leaf, return its single vertex with color c.
• For Branch(left,right), color the new root c, and use Color(left,1-c) and Color(right,1-c) for its constituent trees.

The leaf has no edge to violate the property. At a branch, the induction hypotheses supply the property within each constituent tree. Their roots have color 1-c, so both new edges also join different colors. The construction therefore satisfies the specification for both choices of c.

For Branch(Leaf,Branch(Leaf,Leaf)) with root color 0, the two children receive color 1 and the two grandchildren receive color 0. The strengthened parameter made the recursive step possible.

Now add edges beyond the tree construction. On a triangle, choosing colors 0 and 1 for two adjacent vertices forces the third to be 0 to differ from the second, but it then agrees with the first. The tree result therefore cannot provide the requested coloring for every graph. The new edge condition leads to a different construction or an obstruction, while the tree method retains its original use.