# Can a tree with n vertices be colored with n colors according to greedy coloring?

This question is from a home assignment but it makes no sense to me.

Construct a sequence of trees $(T_n)^∞_{n=1}$ with an ordering of their vertices such that the greedy colouring algorithm uses n colours to find a proper colouring of $T_n$.

From what I can tell, the greedy coloring algorithm always ends up using just two colors when coloring a tree regardless of the ordering of vertices but this question assumes otherwise. Am I wrong? I'm completely stuck on this.

• the greedy coloring algorithm always ends up using just two colors when coloring a tree regardless of the ordering of vertices What if the tree is a path of $4$ vertices, and you color the two end vertices first? How many colors do you end up using in that case?
– bof
Jan 4, 2017 at 19:34
• @bof That still only uses 3 colors for a tree with 4 vertices though, right? Jan 4, 2017 at 19:38
• The problem doesn't say that $T_n$ is a tree with $n$ vertices. Hint: $T_{n+1}$ may have twice as many vertices as $T_n$.
– bof
Jan 4, 2017 at 19:41
• @bof No, but I sort of assumed so based on our lecture notes. The professor uses notation that implies that $T_n$ has $n$ vertices. Partial credit is offered for doing the coloring for $n=2,3,4,5$ too, so it sort of makes sense. Jan 4, 2017 at 19:48
• Your title asks a different question to the one in the body. The number of vertices is specified in the first one and not in the second. Jan 4, 2017 at 19:52

Such a tree $$T_n$$ must have at least $$2^{n-1}$$ vertices. Here is a simple recursive construction where the tree $$T_n$$ has exactly $$2^{n-1}$$ vertices. In each case we order the vertices so that vertices of lower degree are colored before vertices of higher degree.

For $$n=1$$ let $$T_1=P_1=K_1$$.

For $$n=2$$ let $$T_2=P_2=K_2$$.

For $$n=3$$ let $$T_3=P_4$$; it has vertices $$v_1,v_2,v_3,v_4$$ and edges $$v_1v_2,v_2v_3,v_3v_4$$.

For $$n=4$$ start with the tree $$T_3$$ and add new vertices $$v_1',v_2',v_3',v_4'$$ and edges $$v_1v_1',v_2v_2',v_3v_3',v_4v_4'$$.

Edit. As requested in a comment, here is a detailed description and a proof.

Let $$W_1,W_2,W_3,\dots$$ be disjoint sets with $$|W_1|=1$$ and $$|W_n|=2^{n-2}$$ for $$n\ge2$$, so that $$|W_n|=|W_1\cup\cdots\cup W_{n-1}|$$ for $$n\ge2$$. Let $$V_n=W_1\cup\cdots\cup W_n$$.

Let $$E_1=\varnothing$$. For $$n\ge2$$ let $$M_n$$ be a matching between $$W_n$$ and $$V_{n-1}=W_1\cup\cdots\cup W_{n-1}$$ and let $$E_n=E_{n-1}\cup M_n=M_2\cup\cdots\cup M_n$$.

Plainly $$T_n=(V_n,E_n)$$ is a tree of order $$2^{n-1}$$. If $$v\in W_i$$ and $$n\ge i$$, then in the tree $$T_n$$ the vertex $$v$$ has no neighbors in $$W_i$$, exactly one neighbor in $$W_j$$ for each $$j$$ such that $$i\lt j\le n$$, and, if $$i\ge2$$, exactly one neighbor in $$W_1\cup\cdots\cup W_{i-1}$$; thus $$\deg_{T_n}v=\begin{cases} n-1\quad\quad\text{ if }\ \ i=1,\\ n-i+1\ \ \text{ if }\ \ i\ge2.\\ \end{cases}$$ I claim that, if the vertices of $$T_n$$ are ordered so that vertices of lower degree precede vertices of higher degree, then the greedy coloring of $$T_n$$ uses $$n$$ colors.

The proof is by induction on $$n$$. The claim is clearly true for $$T_1=K_1$$ and $$T_2=K_2$$. Suppose $$n\ge3$$. We start by coloring the leaves of $$T_n$$; these are precisely the elements of $$W_n$$, which is an independent set, so they all get the same color, call it red. It remains to color the vertices of $$T_{n-1}$$. Since $$\deg_{T_{n-1}}v=\deg_{T_n}v-1$$ for $$v\in V_{n-1}$$, it follows from the inductive hypothesis that the greedy algorithm on $$T_n$$ will use $$n-1$$ colors on the vertices of $$T_{n-1}$$. Since each vertex of $$T_{n-1}$$ has a neighbor in $$W_n$$, no vertex of $$T_{n-1}$$ is colored red, so a total of $$n$$ colors are used on $$T_n$$.

• i figured out how to construct n=5, 6, etc according to the pattern; and it does work when i color using order from low to high degree by hand--but is there a more rigorous way to write/show that how this ordering leads to the usage of n colours? thanks Mar 29, 2021 at 17:49
• upvoted, thank you so much Apr 6, 2021 at 3:45