Let $G$ be a simple undirected graph with chromatic number $\chi(G)$. Let $G$ has been optimally coloured. Let $T$ be a tree on $\chi(G)$ vertices. Prove that, there exists a subgraph of $G$ which is isomorphic to $T$ and in which each vertex has a different colour.
We'll apply induction on $k=\chi(G)$. If $k=2$, then $G$ is bipartite and the only possible tree with $2$ vertices is just a single edge. Done.
Now suppose the statement holds for $\chi(G)\le k$. Let $G$ be $G$ be a graph with $\chi(G)=k+1$ and it's been coloured with $k+1$ coloured. Then we have a "best" possible partition of $G$ with $k+1$ independent sets i.e. there doesn't exist any partition into independent sets with less that $k+1$ independent sets. Let $V(G)=\bigsqcup_1^{k+1} A_i$ be the partition where $A_i$ contains all vertices of $G$ having colour $i$.
Let $T$ be a tree with $k+1$ vertices. Then there exists a leaf $l$ in $T$. Take $T'=T-l$. Then $T'$ is a tree with $k$ vertices.
Let's take $G'=G-A_{k+1}$. Then $\chi(G')=k$. Then by induction hypothesis $\exists$ a subgraph $H'$ of $G'$ which is isomorphic to $T'$ and have colours $\{1,\ldots,k\}$. Let $f:V(T')\to V(H')$ denotes the isomorphism. Now my idea is to add a vertex from $A_{k+1}$ to $H'$ in such a way that the new subgraph will be isomorphic to $T$.
Let $N(l)=\{v\}$ in $T$. Then $u=f(v)\in V(H')$. Then there exists unique $i\in\{1,\ldots,k\}$ such that $u\in A_i$. So I need to connect a vertex from $A_{k+1}$ to u by a edge in $G$. But the problem is- I don't know whether there is a vertex $w\in A_{k+1}$ such that the edge $wu\in E(G)$.
Can anyone help me complete the proof? Thanks for your help in advance.