Let T be an arbitrary tree. Prove that there is an ordering on the vertices as in Part 1.

Question

This is part 1.

1. Consider the graph above. Give an ordering of the vertices so when you apply the greedy algorithm to color the tree when each new vertex is colored it is connected to exactly one vertex that was colored previously.

So for part 1 the suitable order that I found is $$1 \to 4 \to 2 \to 3 \to 6 \to 9 \to 5 \to 7 \to 8 \to 10 \to 11 \to 12$$ Could someone help me with how I can prove that there is an ordering?

Answer 1

SKETCH: Pick a vertex $v_0$ to be the root. For each vertex $v$ of $T$ there is a unique shortest path $P_v$ from $v_0$ to $v$. ($P_{v_0}$ is the trivial path consisting of the vertex $v_0$ and no edges.) For each integer $\ell\ge 0$ let $T_\ell$ be the set of vertices $v$ of $T$ such that the length of $P_v$ is $\ell$. Thus, $T_0=\{v_0\}$, and $T_1$ contains the vertices connected to $v_0$.

In your example $L_0=\{1\}$, $L_1=\{4\}$, $L_2=\{2,3,6\}$, $L_3=\{9,5,7,8,10\}$, and $L_4=\{11,12\}$.

Now choose any linear ordering $\prec$ of the vertices of $T$ that has the following property:

$$\text{if }u\in L_k,v\in L_\ell,\text{ and }k<\ell,\text{ then }u\prec v\,.$$

In your example you chose the ordering

$$1\prec 4\prec 2\prec 3\prec 6\prec 9\prec 5\prec 7\prec 8\prec 10\prec 11\prec 10\,.$$

Answer 2

Hint 1: You can draw a tree so that it has various levels (and a root).

Hint 2: Here's a coloring of the tree from part 1:

Try to figure out a proof with these hints. If you're still stuck, here's a solution:

Let $T$ be an arbitrary tree, and let $v$ be a vertex of the tree. I claim that if we sort the vertices of the tree by their distance from $v$ (where distance is simply the number of edges we need to traverse to get from $v$ to a given vertex), this provides a satisfactory ordering of the vertices. Note that a vertex that is at a distance $d > 0$ from $v$ has one neighbor (its parent) that is distance $d-1$ from $v$, and all of its other neighbors (its children are at distance $d+1$ from $v$). When we run the greedy algorithm, we first color $v$. For every subsequent vertex $w$, because we color the vertices at a distance $d-1$ before we color the vertices at distance $d$, we must color the parent of $w$ before we color $w$. For the same reason, every other neighbor of $w$ gets colored after $w$. This proves that exactly one vertex connected to $w$ has already been colored, as desired.