 4.03 Planar graph and Euler's formula

Worksheet
Planar graphs
1

Draw an equivalent planar representation for each of the following graphs:

a
b
c
2

State whether the following graphs are planar or non-planar:

a
b
c
3

For each of the following pairs of graphs:

i

Select the connected planar graph.

ii

State the total number of edges, E, of the planar graph.

iii

Calculate D, the sum of the degrees of the vertices of the planar graph.

iv

Hence, write an algebraic equation relating the sum of degrees (D) and the number of edges (E) of the planar graph.

a
A
B
b
A
B
4

For each of the following graphs:

i

Draw an equivalent planar representation.

ii

Determine the number of faces f for the representation.

a
b
c
d
Euler's formula
5

Consider the following graphs:

Graph A

Graph C

Graph B

Graph D

Copy and complete the table below:

6

For each of the following graphs:

i

State v, the number of vertices.

ii

State e, the number of edges.

iii

Draw an equivalent planar representation of the graph.

iv

State f, the number of faces of the planar graph.

v

Evaluate v + f - e for the planar graph.

a
b
c
7

Consider the following graphs:

Graph A

Graph C

Graph B

Graph D

a

Complete the table below:

b

What do you notice about the number of vertices with odd degree?

8

Determine whether a connected planar graph could have the following parameters:

a
v = 5, f = 6, and e = 9
b
v = 5, f = 5, and e = 10
c
v = 8, f = 6, and e = 13
d
v = 12, f = 10, and e = 20
9

For a connected planar graph with v vertices, e edges and f faces, find:

a
f given v=7 and e=14
b
e given v=8 and f=2
c
v given f=3 and e=12
d
e given v=4 and f=5
e
v given f=8 and e=11
f
f given v=6 and e=7
10

A connected planar graph has 3 edges and 1 vertex.

a

Find f, the number of faces.

b

Draw a planar graph with the given parameters.

11

A connected planar graph has 3 vertices and 3 faces.

a

Find the number of edges, e.

b

Draw a planar graph with the given parameters.

12

A connected planar graph has 3 edges and 3 faces.

a

Find the number of vertices, v.

b

Draw a planar graph with the given parameters.

13

For the following non-planar graphs, determine the minimum number of edges that can be removed to make them planar:

a
b
14

A connected planar graph has 4 vertices of degrees 2, 2, 3, and 3.

a

Find the number of edges, e.

b

Find the number of faces, f.

Outcomes

ACMGM081

explain the meaning of the terms: planar graph, and face

ACMGM082

apply Euler’s formula, v+f−e=2, to solve problems relating to planar graphs