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?
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.
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.
If a graph is not planar, then there are no faces to define - the crossing of edges makes it impossible.
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-e+f=2$v−e+f=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 write
$v-e+f=2$v−e+f=2
$6-9+5=2$6−9+5=2
$2=2$2=2
This is true, therefore Euler's formula holds.
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-e+f=2$v−e+f=2 hold?
Do: $6-8+3\ne2$6−8+3≠2, so the network does not satisfy Euler's formula.
Write: 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-e+f=2$v−e+f=2 hold?
Do: $2-3+3=2$2−3+3=2
Write: The network satisfies Euler's formula, therefore it is planar.
Note: 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
Consider the graph shown below.
Match the graph with its equivalent planar representation.
A
B
C
DHow many faces $f$f does this representation have?
Question 2
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.
D
Question 3
A connected planar graph has $14$14 edges, and $7$7 vertices. Solve for $f$f, the number of faces.