Problem Set 3

This problem set does not contribute to your final course grade, but is useful practice writing proofs for the exam. It is due in class on Friday, March 11.

Question 1

Using Kuratowski’s theorem, prove the following graph is nonplanar:

Question 2

Draw $K_{4,4}$ on the torus so that no edges cross.

Question 3

The genus $g(\Gamma)$ of a graph $\Gamma$ is the minimum number $n$ so that $\Gamma$ can be drawn on a surface of genus $n$ without any edges crossing, but not on a surface of genus $k$ for any $k<n$.

Prove that $g(K_n)\geq (n-3)(n-4)/12.$