1.II .17F

Graph Theory | Part II, 2008

State a result of Euler concerning the number of vertices, edges and faces of a connected plane graph. Deduce that if GG is a planar graph then δ(G)5\delta(G) \leqslant 5. Show that if GG is a planar graph then χ(G)5\chi(G) \leqslant 5.

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 GG is a graph with χ(G)4\chi(G) \leqslant 4 then GG is planar.

(ii) If GG is a connected graph with average degree at most 2.012.01 then GG is planar.

(iii) If GG is a connected graph with average degree at most 2 then GG is planar.

Typos? Please submit corrections to this page on GitHub.