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.
Best Answer
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$.