Section 9: Planar graphs

Question 1

Planar graph

Answer 1

a graph that can be drawn in the plane in such a way that no edges cross
each other, and no edge touches a vertex other than its endpoints

Question 2

An edge e and a region a are incident if

Answer 2

e forms part of the boundary of a

Question 3

Degree of a region d(a)

Answer 3

the number of edges incident with it

Question 4

Let G = (V, E) be a planar graph, and suppose that A is the set of regions in a planar drawing of G. Express a relationship between the degree of the regions and edges

Answer 4

∑ d(a) = 2|E|
a∈A

Question 5

Relationship beween shortest cycle in a planar graph and degree of each region

Answer 5

If the shortest cycle in G has length d, then, in any planar drawing of G, every region has degree at least d.

Question 6

Euler’s Formula

Answer 6

Let G be a non-empty, connected planar graph with n vertices and m edges, and suppose there is a planar drawing of G with r regions. Then
n − m + r = 2.

Question 7

Inequality for vertices and edges

Answer 7

Let G be a connected planar graph with n≥3 vertices and m edges. Then m ≤ 3n−6.

Question 8

Degree of a vertex in connected planar graph

Answer 8

Let G = (V, E) be a connected planar graph. Then G contains a vertex v such that d(v) ≤ 5.

Question 9

Six colour theorem

Answer 9

Let G be a planar graph. Then the chromatic number of G is at most six.