In addition to being able to draw graphs on the projective plane and the Klein Bottle, the big source of problems this week is applications of Euler’s formula $e-v+f=2$.

Annoying to draw

Show that $K_{4,4}$ can be drawn on the Klein bottle (Hints: may help to draw the 4 vertices in a regular octagon in the middle of the Klein bottle. Every face will have degree 4).

Proof 1

Use Euler’s formula and handshaking to give another proof that $K_{3,3}$ isn’t planar. (Note: at the beginning of lecture in Week 9 we will use this method to prove that $K_5$ isn’t planar; if you’re stuck waiting until then may help. The idea is that you know how many vertices and edges $K_{3,3}$ has, and since any face of $K_{3,3}$ must have at least 4 edges ( why?), it can’t have too many faces…)

Proof 2

Suppose that $G$ is a connected graph drawn in the plane, so that every vertex has the same degree $d_1$, and every face has the same degree $d_2$. Prove that

and give an example of such a graph for each pair.