4.03 Planar graph and Euler's formula

Planar graphs

You may have noticed that graphs often have their edges crossing over each other. If it is possible to move the vertices into a configuration so that no edges cross each other it is called a planar representation, and the graph is called a planar graph.

It isn’t always obvious at first glance whether a graph is planar or non-planar - sometimes you have to move the vertices around for a long time before none of the edges cross.

The top graph is planar, and below it are three of its equivalent planar representations.

Here are two simple graphs. Use the applet to drag the vertices. Can you work out whether they are planar?

Created with Geogebra

Created with Geogebra

Faces

Once a planar graph is organised into a planar representation, we can define a face (or region) as the area of the plane bounded by edges. Important! The part of the plane outside the graph is also a face.

Non-simple graphs that are planar also have faces, though some of their faces are bounded by only one or only two edges:

 

Euler's formula

The Swiss mathematician Leonhard Euler (pronounced “OIL-er”) was a pioneer in the mathematics of networks in the 18th century. He noticed something interesting about networks that are connected and planar, which is that the number of vertices $v$v, the number of edges $e$e, and the number of faces $f$f, satisfy the formula:

$v+f-e=2$v+f−e=2.

We call this formula Euler's formula.

Consider this planar network:

It has $6$6 vertices, $9$9 edges, and $5$5 faces.

To show that Euler's formula holds for this graph we can evaluate the left-hand side of the formula and show this is equal to $2$2:

$v+f-e$v+f−e	$=$=	$6+5-9$6+5−9
	$=$=	$2$2

Therefore Euler's formula holds for this graph.

 

Worked examples

Example 1

Is there a connected, planar network that has $6$6 vertices, $8$8 edges, and $3$3 faces?

Think: Check does Euler's rule $v+f-e=2$v+f−e=2 hold?

Do: ,

$v+f-e$v+f−e	$=$=	$6+3-8$6+3−8
	$=$=	$1$1

Since $v+f-e\ne2$v+f−e≠2, the network does not satisfy Euler's formula and there is not a connected, planar network with these properties. 

Example 2

A connected network has $2$2 vertices, $5$5 edges, and $5$5 faces. Is it planar?

Think: Planar graphs satisfy Euler's rule. Check does the rule $v+f-e=2$v+f−e=2 hold?

Do: 

$v+f-e$v+f−e	$=$=	$2+5-5$2+5−5
	$=$=	$2$2

Since $v+f-e=2$v+f−e=2, the network satisfies Euler's formula and is therefore planar.

Reflect: There is only one simple, connected network with two vertices - it has exactly one edge joining both vertices together. This means the network we are looking for will not be simple. Here is an example of a non-simple network with $2$2 vertices, $5$5 edges and $5$5 faces:

 

 

Practice questions

Question 1

Question 2

Question 3