(a) Define the Ramsey number $R(k)$ and show that $R(k) \leqslant 4^{k}$.

Show that every 2-coloured complete graph $K_{n}$ with $n \geqslant 2$ contains a monochromatic spanning tree. Is the same true if $K_{n}$ is coloured with 3 colours? Give a proof or counterexample.

(b) Let $G=(V, E)$ be a graph. Show that the number of paths of length 2 in $G$ is

$$\sum_{x \in V} d(x)(d(x)-1) .$$

Now consider a 2-coloured complete graph $K_{n}$ with $n \geqslant 3$. Show that the number of monochromatic triangles in $K_{n}$ is

$$\frac{1}{2} \sum_{x}\left\{\left(\begin{array}{c} d_{r}(x) \\ 2 \end{array}\right)+\left(\begin{array}{c} d_{b}(x) \\ 2 \end{array}\right)\right\}-\frac{1}{2}\left(\begin{array}{l} n \\ 3 \end{array}\right)$$

where $d_{r}(x)$ denotes the number of red edges incident with a vertex $x$ and $d_{b}(x)=$ $(n-1)-d_{r}(x)$ denotes the number of blue edges incident with $x$. [Hint: Count paths of length 2 in two different ways.]