1.II .17F
Part II, 2008
State a result of Euler concerning the number of vertices, edges and faces of a connected plane graph. Deduce that if is a planar graph then . Show that if is a planar graph then .
Are the following statements true or false? Justify your answers.
[You may quote standard facts about planar and non-planar graphs, provided that they are clearly stated.]
(i) If is a graph with then is planar.
(ii) If is a connected graph with average degree at most then is planar.
(iii) If is a connected graph with average degree at most 2 then is planar.