Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/ii/paper-1/17f/iii/solution
Past exam of the mathematics course of the University of Cambridge 2008 ii Paper 1 17F iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
True for finite connected simple graphs. average degree of a graph at most two implies . A spanning tree has edges, leaving at most one extra edge. Hence the graph is a tree or unicyclic. trees are planar, and a unicyclic graph is a cycle with trees attached to its vertices, which can also be embedded in the plane. Connectedness is essential to this argument: a disconnected nonplanar component can be diluted by isolated vertices.
New to topics? Read the docs here!