Past exam of the probability, statistics and options I course of the University of Oxford / 2010 / R / 1 (R1)

Count facial boundary walks with each edge-side counted once. Their total length is $2m$. Every face walk has length at least four: simplicity excludes loops and parallel-edge two-cycles, absence of triangles excludes length three, and a length-two face walk consisting solely of a bridge traversed twice could be the whole boundary only for the excluded connected graph on two vertices. Bridges may occur twice in a longer boundary walk and are still correctly counted. Thus $4f\le 2m$.

The Euler formula for a connected planar graph gives $2=n-m+f\le n-m+m/2=n-m/2$. Rearranging yields

The complete bipartite graph $K_{3,3}$ is connected, simple, and has no triangles because all its cycles have even length. It has $n=6$ vertices and $m=9$ edges. A planar drawing would require $9\le 2\cdot 6-4=8$ by part (i), a contradiction. Therefore $K_{3,3}$ is nonplanar.

The modified graph is planar. Place $x_1=(-2,0)$ and $x_2=(2,0)$, and place the other vertices on the vertical line between them in the bottom-to-top order $y_2,y_1,y_5,y_3,y_4$. Draw each edge $x_i{y}_j$ as a straight segment. Each half of the drawing is a fan sharing one endpoint, so its edges do not cross. The added edges $y_2{y}_1$ and $y_1{y}_5$ are consecutive vertical segments, meeting other edges only at their endpoints. The following original drawing exhibits the embedding.

A triangle $x_1{y}_1{y}_2$ forces at least three vertex colours. Three suffice: colour $x_1,x_2$ blue; $y_1,y_3,y_4$ orange; and $y_2,y_5$ green, as in the drawing. Hence the chromatic number is three.

The five edges incident to $x_1$ force at least five edge colours. An explicit proper five-edge-colouring is

Give $y_1{y}_2$ colour 5 and $y_1{y}_5$ colour 3. At $y_1$ the incident colours are $1,2,5,3$; at $y_2$ they are $2,3,5$; at $y_5$ they are $5,1,3$; all are distinct. The two remaining vertices each have two distinct incident colours. Thus the edge chromatic number is five.