(i) State and prove a necessary and sufficient condition for a graph to be Eulerian (that is, to have an Eulerian circuit).

Prove that, given any connected non-Eulerian graph $G$, there is an Eulerian graph $H$ and a vertex $v \in H$ such that $G=H-v$.

(ii) Let $G$ be a connected plane graph with $n$ vertices, $e$ edges and $f$ faces. Prove that $n-e+f=2$. Deduce that $e \leq g(n-2) /(g-2)$, where $g$ is the smallest face size.

The crossing number $c(G)$ of a non-planar graph $G$ is the minimum number of edgecrossings needed when drawing the graph in the plane. (The crossing of three edges at the same point is not allowed.) Show that if $G$ has $n$ vertices and $e$ edges then $c(G) \geq e-3 n+6$. Find $c\left(K_{6}\right)$.