Computer Science 260
Assignment 7
1. Prove that a graph G = (V,E) is connected if and only if for every partition of V
into two nonempty sets V1 and V2 (V1 \ V2 = ; and V1 [ V2 = V ), there is an edge with
one end in V1 and one end in V2. (10 marks)
2. In a plane drawing of a simple connected planar graph with at least three vertices,
every face is bounded by at least 3 edges and every edge separates at most 2 faces.
Therefore 2e 3f. Substituting into euler’s formula v e + 2e
3 2, or e 3v 6. By
the handshake theorem the average degree in a graph is 2e
v . Thus in a simple planar
graph the average degree is at most 2(3v6)
v = 6 12
v . Since the average degree in a
simple planar graph is less than 6, and since every vertex cannot have above average
degree, in any simple planar graph there exists a vertex of degree at most 5.
A legal coloring of a graph is an assignment of colors to vertices so that adjacent vertices
receive di↵erent colors. A graph is k-colorable i↵ it is possible to legally color the vertices
using at most k colors.
Prove using mathematical induction that every simple planar graph is 6-colorable. (8
marks)
