(i) Prove that any graph $G$ drawn on a compact surface $S$ with negative Euler characteristic $E(S)$ has a vertex colouring that uses at most

$$h=\left\lfloor\frac{1}{2}(7+\sqrt{49-24 E(S)})\right\rfloor$$

colours.

Briefly discuss whether the result is still true when $E(S) \geqslant 0$.

(ii) Prove that a graph $G$ is $k$ edge-connected if and only if the removal of no set of less than $k$ edges from $G$ disconnects $G$.

[If you use any form of Menger's theorem, you must prove it.]

Let $G$ be a minimal example of a graph that requires $k+1$ colours for a vertex colouring. Show that $G$ must be $k$ edge-connected.