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)