8.03 Planar graphs and Euler's formula

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 equivalent planar representations. All four graphs are isomorphic.

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.

In all three planar representations of the network from earlier, each face has been given a different colour - this network has 4 faces.

The octahedral graph below (which represents a 3-dimensional octahedron solid) has 8 faces.

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

The network on the left has 6 faces, with 4 of them bounded by only 1 edge (loops). The network on the right has 5 faces, with 2 of them bounded by only 2 edges.

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

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

We call this formula Euler's formula.

This is a planar network.

It has 6 vertices, 5 faces, and 9 edges, applying Euler's we obtain: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

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

Examples

Example 1

Consider the graph shown below.

a

Match the graph with its equivalent planar representation.

A

B

C

D

Worked Solution

Create a strategy

Redraw the edges that are crossing each other on the given graph. Make sure that the vertices that were connected by an edge on the original graph are still connected on the planar graph.

Apply the idea

All the graphs among the options do not contain any intersecting edges. So they are all planar graphs.

Only the graph in option A has the same edges, HD and BF, as in the original graph.

So the correct answer is option A.

Watch question walkthrough

b

How many regions does this representation have?

Worked Solution

Create a strategy

Use the Euler's formula for a connected planar graph given by:V+F-E=2 where V is the number of vertices, F is the number of faces, and E is the number of edges.

Apply the idea

We are given V=8 and E=10.

\displaystyle V+F-E	\displaystyle =	\displaystyle 2	Write the formula
\displaystyle 8+F-10	\displaystyle =	\displaystyle 2	Substitute V and E
\displaystyle -2 +F	\displaystyle =	\displaystyle 2	Evaluate
\displaystyle F	\displaystyle =	\displaystyle 4	Add 2 to both sides

Watch question walkthrough

Example 2

Consider the following graphs.

A

B

C

D

a

Complete the table for the graphs.

\text{Graph}	\text{Vertices } (V)	\text{Faces } (F)	\text{Edges } (E)	V+F-E	\text{Planar?} \\ \text{(Y/N)}	\text{Number of} \\ \text{vertices with} \\ \text{odd degree}
\quad \text{A}
\quad \text{B}
\quad \text{C}
\quad \text{D}

Worked Solution

Create a strategy

Count the number of vertices, faces, and edges in each graph to fill in the table.

Apply the idea

For graph A, we can see that it is planar and V=5, \, F=5, and E=8. So:

\displaystyle V+F-E	\displaystyle =	\displaystyle 5+5-8	Substitute V,\, F, and E
	\displaystyle =	\displaystyle 2	Evaluate

Since we get 2, Euler's formula holds and Graph A must be planar.

Graph A has 4 vertices with odd degree which are A, \, B, \, C, and D.

Similarly doing this for graphs B, C and D we have the completed table:

\text{Graph}	\text{Vertices } (V)	\text{Faces } (F)	\text{Edges } (E)	V+F-E	\text{Planar?} \\ \text{(Y/N)}	\text{Number of} \\ \text{vertices with} \\ \text{odd degree}
\quad \text{A}	5	5	8	2	Y	4
\quad \text{B}	5	4	7	2	Y	4
\quad \text{C}	4	4	6	2	Y	4
\quad \text{D}	8	7	13	2	Y	2

b

Which of the following statements is true?

A

Connected planar graphs can have any number of vertices with odd degrees.

B

Connected planar graphs have an even number of vertices that have odd degrees.

C

Connected planar graphs have an odd number of vertices that have odd degrees.

D

Connected planar graphs have two vertices with odd degrees.

Worked Solution

Create a strategy

Compare the results for each graph from the table.

Apply the idea

Based on the results from the table in part (a), we can see that graphs A, \, B, \, C, and D are all planar and satisfy the Euler's formula.

Notice also that:

• Graph A has 4 odd degree vertices.

• Graph B has 4 odd degree vertices.

• Graph C has 4 odd degree vertices.

• Graph D has 2 odd degree vertices.

We can conclude that connected planar graphs have an even number of vertices that have odd degrees.

So the correct answer is option B.

Example 3

A connected planar graph has 11 edges, and 5 vertices. Solve for R, the number of regions.

Worked Solution

Create a strategy

Use the Euler's formula: V+R-E=2 where V is the number of vertices, R is the number of regions, and E is the number of edges.

Apply the idea

\displaystyle V+R-E	\displaystyle =	\displaystyle 2	Write the formula
\displaystyle 5+R-11	\displaystyle =	\displaystyle 2	Substitute V=5 and E=11
\displaystyle R-6	\displaystyle =	\displaystyle 2	Subtract like terms
\displaystyle R	\displaystyle =	\displaystyle 8	Add 6 to both sides

Watch question walkthrough