Planar Graphs

Planar graphs can be drawn so that edges ONLY intersect at the vertices. This means that there CANNOT be any intersections where there is no vertex.

Essential Further Mathematics 4ed 2012 (Fig 23.13)

The above graph is NOT a planar graph, because there are edges that cross one another, and not at the vertices.

NOTE: Even though graphs may seem to be not planar, they sometimes can be drawn so that they are planar.  These types of questions usually pop up in VCAA MCQ’s and have often tricked people.

Euler’s Formula

Euler’s formula can be used to determine if a graph is planar or not.

Euler’s formula:

Where:

v = the number of vertices

e = the number of edges

f = the number of faces/regions