8.03 Planar graphs and Euler's formula

Planar networks

Networks can often have their edges crossing over each other. But maybe there’s a way to move the vertices into a certain configuration so that none of the edges cross each other anymore. Such a configuration is called a planar representation, and networks that have one are called planar networks.

It isn’t always obvious at first glance whether a network is planar or non-planar - sometimes you have to move the vertices around for a long time before none of the edges cross each other anymore. Recall that rearranging the vertices and edges while maintaining the same connectivity will lead to creating isomorphic(equivalent) graphs.

 

The top network is planar, and below it are three of its planar representations. All four graphs are isomorphic.

Here are three simple networks; two are planar and one is not. Can you figure out which is which?

Created with Geogebra

Created with Geogebra

Created with Geogebra

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

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

However, if a network is not planar, then there are no faces to define - the crossing of edges makes it impossible.

If you’re ready for a challenge, see if you can sort the three planar networks from the two non-planar networks in these applets:

Created with Geogebra

Created with Geogebra

Created with Geogebra

Created with Geogebra

Created with Geogebra

How many faces do the planar networks have? Don't forget to count the exterior space as $1$1 face. This can be very time consuming and perhaps you have just spent a very long time manipulating a non-planar network!! There is a simple way to check if something is planar or not.

 

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 faces $F$F, and the number of edges $E$E, satisfy the formula:

$V+F-E=2$V+F−E=2.

We call this formula Euler's formula.

This is a planar network:

It has $6$6 vertices, $5$5 faces, and  $9$9 edges, applying Euler's we obtain:

$6+5-9=2$6+5−9=2

Let’s try again with the octahedral network:

Euler’s formula only works with planar networks, and this doesn’t look planar - the edges cross each other! But even though this is not a planar representation, we can check if there is one by checking if the formula it true.

 

$6+8-12=2$6+8−12=2

It is true so this is a planar network we would now need to find the planar representation.

 

Worked example

Example 1

A connected, planar network has $5$5 vertices and $5$5 faces. How many edges does it have?

We know $V=5$V=5 and $F=5$F=5. This means $V+F-E=2$V+F−E=2

becomes $5+5-E=2$5+5−E=2
Adding $E$E and subtracting $2$2 from both sides and rearranging gives $E=8$E=8

So the network has $8$8 edges.

 

Here are two different networks that are connected, planar, and have $5$5 vertices, $8$8 edges, and $5$5 faces:

They also happen to be simple. There are plenty of other examples, including some that aren’t simple, like this one:

This formula also rules out certain networks. Let's take a look at some examples.

 

Worked examples

Example 2

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

No, because $6+3-8\ne2$6+3−8≠2 , using $V+F-E=2$V+F−E=2

Example 3

Is there a connected, planar network that has $12$12 vertices, $30$30 edges, and $20$20 faces?

Using $V+F-E=2$V+F−E=2 to check we can see that $12+20-30=2$12+20−30=2, so yes there is a connected planar network that meets this condition.

Here’s a network that illustrates Example 3

 

Example 4

Is there a connected, planar network that has $2$2 vertices, $5$5 edges, and $5$5 faces?

Yes, because $2+3-3=2$2+3−3=2. (again using $V+F-E=2$V+F−E=2)

 

There is only one simple, connected network with two vertices - it has exactly one edge joining both vertices together, and is pretty boring. 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