This is part 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?