Australian Curriculum 12 General Mathematics - 2020 Edition

4.03 Planar graph and Euler's formula

Lesson

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?

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**.

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

*The octahedral graph (which represents a $3$3-dimensional octahedron solid) has *$8$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$6* faces, with *$4$4* of them bounded by only *$1$1* edge (where there are loops). The graph on the right has *$5$5* faces, with *$2$2* of them bounded by only *$2$2* edges.*

Non-planar graphs

If a graph 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$`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.

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.

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:

Consider the graph shown below.

Match the graph with its equivalent planar representation.

ABCDABCDHow many faces $f$

`f`does this representation have?

Consider the following graphs.

$A$A |
$B$B |
$C$C |
$D$D |

Fill in the table for the graphs.

Graph Vertices Faces Edges $v+f-e$ `v`+`f`−`e`Planar? (Y/N) Number of vertices with odd degree $A$ `A`$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $B$ `B`$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $C$ `C`$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $D$ `D`$\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ Which of the following statements is true?

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

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

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

CConnected planar graphs have two vertices with odd degrees.

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

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

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

CConnected planar graphs have two vertices with odd degrees.

D

A connected planar graph has $14$14 edges, and $7$7 vertices. Solve for $f$`f`, the number of faces.

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

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