4.03 Planar graph and Euler's formula

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.

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. The part of the plane outside the graph is also a face.

In all three planar representations of the graph from earlier, each face has been given a different colour below.

From the 4 colours, we can see that the above graph has 4 faces.

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

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

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

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

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 C has the same edges, HD and BF, as in the original graph.

So the correct answer is option C.

b

How many faces f does this representation have?

Worked Solution

Create a strategy

Count the number of regions the plane is divided into, including the part of the plane outside the graph.

Apply the idea

There are 4 regions in the graph. 2 inside the rectangle. 1 between the rectangle and the edge BF. And 1 on the outside of the graph.

So f=4.

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 edges e, and the number of faces f, satisfy the formula:v+f-e=2

We call this formula Euler's formula.

Consider this planar network.

It has 6 vertices, 9 edges, and 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:

Therefore Euler's formula holds for this graph. So it is planar.

Examples

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