Graphs and NetworksPlanar Graphs
Here is another puzzle that is related to graph theory.
In a small village there are three utility plants producing water, electricity and gas respectively. There are also three houses which need to be served. Unfortunately, due to the city’s layout, the pipes or cables for every product are not allowed to cross.
Try to connect each of the plants below to each of the houses, without any of your lines crossing:
Just like the Königsberg bridges before, you quickly discover that this problem is also impossible. It seems that some graphs can be drawn without overlapping edges – these are called planar graphs – but others cannot.
The graph in the three utilities puzzle is the
This is a planar graph, but the
All planar graphs divide the plane they are drawn on into a number of areas, called faces.
11 Vertices + Faces
15 Vertices + Faces
25 Vertices + Faces
When comparing these numbers, you will notice that the number of edges is always
Unfortunately, there are infinitely many graphs and we can’t check every one to see if Euler’s equation works. Instead we can try to find a simple
0 + 1 = 0 + 1
Any (finite) graph can be constructed by starting with one vertex and adding more vertices one by one. We have shown that, whichever way we add new vertices, Euler’s equation is valid. Therefore it is valid for all graphs.
The process we have used is called mathematical induction. It is a very useful technique for proving results in infinitely many cases, simply by starting with the simplest case, and showing that the result holds at every step when constructing more complex cases.
Many planar graphs look very similar to the nets of
This means that we can use Euler’s formula not only for planar graphs but also for all polyhedra – with one small difference. When transforming the polyhedra into graphs, one of the faces disappears: the topmost face of the polyhedra becomes the “outside”; of the graphs.
In other words, if you count the number of edges, faces and vertices of any polyhedron, you will find that F + V = E +