Planar Graphs and Euler’s Formula Revision Notes for VCE SSCE General Mathematics

Planar Graphs and Euler's Formula

Introduction to planar graphs

A planar graph is a graph that can be drawn on a flat surface so that no edges cross over each other, except where they meet at vertices. This is an important property in graph theory because it helps us understand the structure and relationships within networks.

What makes a graph planar?

The key characteristic of a planar graph is that when drawn properly, edges only intersect at the vertices (the points or nodes). Look at this example:

This graph is planar because we can see all four vertices (A, B, C, D) connected by edges that don't cross anywhere except at the vertices themselves.

infoNote

The key to identifying a planar graph is checking whether all edge intersections occur only at vertices. If edges cross anywhere else, the graph either needs to be redrawn or is non-planar.

Equivalent planar forms

Some graphs might not look planar at first glance, but they can be redrawn to show their planar nature. When two graphs have the same connections between vertices but are drawn differently, they are called equivalent or isomorphic graphs.

Consider these two graphs:

Graph 1 appears to have crossing edges, but Graph 2 shows the same graph redrawn in a way that clearly demonstrates it is planar. The connections between vertices A, B, C, D, E, and F are identical in both graphs, just arranged differently.

infoNote

Two graphs are equivalent (isomorphic) when they represent the same connections between vertices, even if they look different visually. The arrangement may change, but the underlying structure remains the same.

Non-planar graphs

Not every graph can be redrawn in planar form. Some graphs will always have crossing edges no matter how you arrange them. Here's an example of a non-planar graph:

chatImportant

This graph with vertices A, B, C, D, and E cannot be redrawn without edges crossing. No matter how you rearrange it, you'll always have at least one pair of edges that intersect away from the vertices. Some graphs are inherently non-planar.

Redrawing graphs in planar form

Sometimes you need to redraw a graph to reveal its planar nature. Here's a systematic approach:

Step-by-step method

Step 1: Identify which edge is causing the intersection problem and temporarily remove it.

Step 2: Redraw the remaining graph structure.

Step 3: Add back the removed edge as a curved line that avoids crossing the other edges.

lightbulbExample

Worked Example: Redrawing a Graph

Let's redraw this graph in planar form:

Solution:

First, we identify that edge DB intersects edge AC. We remove edge DB and redraw the graph.

Then we add edge DB back as a curved line that doesn't cross any other edges. The result is an equivalent planar form where no edges intersect except at vertices.

Faces of a graph

When a planar graph is drawn, it divides the surface into distinct regions called faces.

What is a face?

A face is a region of space created by the graph. This includes:

Areas enclosed by the edges of the graph
The infinite region surrounding the entire graph

The surrounding region is called the infinite face and must always be counted when determining the total number of faces.

chatImportant

Don't forget the infinite face!

When counting faces, students often forget to include the infinite region that surrounds the entire graph. This is a common mistake that will lead to incorrect results when using Euler's formula. Always count the infinite face as one of your faces.

Counting faces

Let's look at some examples to understand how to count faces.

Example with 2 faces:

A simple triangular graph creates two faces:

$f_1$ : the area inside the triangle
$f_2$ : the infinite area outside the triangle

Example with 4 faces:

This more complex graph divides the surface into four distinct faces:

$f_1$ : the blue quadrilateral region on the left
$f_2$ : the orange triangular region in the centre
$f_3$ : the light green triangular region on the right
$f_4$ : the infinite region surrounding the entire graph

infoNote

Exam tip: Always mark the faces on your diagram when counting them. Use different colours or labels to distinguish each region clearly. This visual approach helps prevent counting errors and ensures you don't miss the infinite face.

Euler's formula

Euler discovered a remarkable relationship between the number of vertices, edges, and faces in any connected planar graph.

The formula

For a connected planar graph:

$v + f = e + 2$

Where:

$v$ = number of vertices
$e$ = number of edges
$f$ = number of faces

In words: number of vertices + number of faces = number of edges + 2

infoNote

Why is Euler's formula important?

This formula works for any connected planar graph, no matter how simple or complex. It provides a way to check your work when analyzing graphs, or to find an unknown property when you know the other two. This makes it an incredibly powerful tool in graph theory.

Understanding the formula

Let's verify the formula with a quick example. Consider a graph with:

$v = 6$ vertices
$e = 8$ edges
$f = 4$ faces

Verifying Euler's formula:

$v + f = e + 2$

$6 + 4 = 8 + 2$

$10 = 10$ ✓

The formula is confirmed!

Verifying Euler's formula

Let's work through some examples to practice verifying Euler's formula.

lightbulbExample

Worked Example 1: Simple Verification

Consider this connected planar graph:

Step 1: Count the vertices.

There are four vertices: A, B, C, D

Therefore $v = 4$

Step 2: Count the edges.

The edges are: AB, AC, AD, BC (appears twice), and BD

Therefore $e = 6$

Step 3: Count the faces.

Mark the faces on the diagram to help count them. Remember to include the infinite face surrounding the graph.

There are four faces: $f_1$ , $f_2$ , $f_3$ , and $f_4$ (infinite face)

Therefore $f = 4$

Step 4: Verify Euler's formula.

$v + f = e + 2$

$4 + 4 = 6 + 2$

$8 = 8$ ✓

Therefore Euler's formula is verified.

lightbulbExample

Worked Example 2: Graph Requiring Redrawing

Consider this connected planar graph:

Step 1: Count the vertices.

There are five vertices: A, B, C, D, E

Therefore $v = 5$

Step 2: Count the edges.

The edges are: AC, AD, AE, BC, BE, CD, DE

Therefore $e = 7$

Step 3: Count the faces.

This graph has crossing edges, so we need to redraw it in planar form to accurately count the faces:

Now we can clearly see four faces: $f_1$ , $f_2$ , $f_3$ , and $f_4$ (infinite face)

Therefore $f = 4$

Step 4: Verify Euler's formula.

$v + f = e + 2$

$5 + 4 = 7 + 2$

$9 = 9$ ✓

Therefore Euler's formula is verified.

Using Euler's formula to find unknown properties

Euler's formula can be rearranged algebraically to find any unknown property of a planar graph when you know the other two properties.

lightbulbExample

Worked Example 3a: Finding the Number of Edges

For a planar connected graph with 4 vertices and 6 faces, find the number of edges.

Step 1: Write down the known values.

$v = 4$ , $f = 6$

Step 2: Write Euler's formula.

$v + f = e + 2$

Step 3: Substitute the known values.

$4 + 6 = e + 2$

$10 = e + 2$

Step 4: Solve for $e$ .

$e = 10 - 2$

$e = 8$

Answer: Therefore this graph has 8 edges.

lightbulbExample

Worked Example 3b: Finding the Number of Faces

For a planar connected graph with 4 vertices and 5 edges, find the number of faces.

Step 1: Write down the known values.

$v = 4$ , $e = 5$

Step 2: Write Euler's formula.

$v + f = e + 2$

Step 3: Substitute the known values.

$4 + f = 5 + 2$

$4 + f = 7$

Step 4: Solve for $f$ .

$f = 7 - 4$

$f = 3$

Answer: Therefore this graph has 3 faces.

lightbulbExample

Worked Example 3c: Finding the Number of Vertices

For a planar connected graph with 5 faces and 8 edges, find the number of vertices.

Step 1: Write down the known values.

$f = 5$ , $e = 8$

Step 2: Write Euler's formula.

$v + f = e + 2$

Step 3: Substitute the known values.

$v + 5 = 8 + 2$

$v + 5 = 10$

Step 4: Solve for $v$ .

$v = 10 - 5$

$v = 5$

Answer: Therefore this graph has 5 vertices.

bookmarkSummary

Key Points to Remember:

A planar graph can be drawn on a flat surface with no edges crossing, except at vertices
Some graphs that appear non-planar can be redrawn in an equivalent planar form
A face is a region of space created by the graph, including the infinite region surrounding it
Always count the infinite face when determining the total number of faces
Euler's formula states: $v + f = e + 2$ for connected planar graphs
You can use Euler's formula to verify your graph analysis or find an unknown property
When counting faces, it often helps to redraw the graph in clear planar form first

Planar Graphs and Euler’s Formula (VCE SSCE General Mathematics): Revision Notes