(a) Show that every finite tree of order at least 2 has a leaf. Hence, or otherwise, show that a tree of order $n \geqslant 1$ must have precisely $n-1$ edges.

(b) Let $G$ be a graph. Explain briefly why $|G| / \alpha(G) \leqslant \chi(G) \leqslant \Delta(G)+1$.

Let $k=\chi(G)$, and assume $k \geqslant 2$. By induction on $|G|$, or otherwise, show that $G$ has a subgraph $H$ with $\delta(H) \geqslant k-1$. Hence, or otherwise, show that if $T$ is a tree of order $k$ then $T \subseteq G$.

(c) Let $s, t \geqslant 2$ be integers, let $n=(s-1)(t-1)+1$ and let $T$ be a tree of order $t$. Show that whenever the edges of the complete graph $K_{n}$ are coloured blue and yellow then it must contain either a blue $K_{s}$ or a yellow $T$.

Does this remain true if $K_{n}$ is replaced by $K_{n-1}$ ? Justify your answer.

[The independence number $\alpha(G)$ of a graph $G$ is the size of the largest set $W \subseteq V(G)$ of vertices such that no edge of $G$ joins two points of $W$. Recall that $\chi(G)$ is the chromatic number and $\delta(G), \Delta(G)$ are respectively the minimal/maximal degrees of vertices in $G$.]