Articles
It was a trick question!
It is impossible to draw K5 on a piece of paper without any edges crossing each other.
K5 is called a non-planar graph because it cannot be drawn in a 2-dimensional plane without any edges intersecting.
Every complete graph that is larger than K4 is non-planar and so cannot be drawn on paper without some edges crossing.
It can be fun to challenge people who do not know this fact to join five dots together without any lines crossing.
It is amazing how long some people will try the impossible, convinced that they are getting close to ‘cracking it’. It is one of those problems that looks as though it must be possible somehow, especially when you only need to draw one more line to complete the puzzle.
The proof that K5 is non-planar uses a very interesting property common to all simple planar graphs.
V - E + F = 2
where:
V = no. of vertices E = no. of edges,
F = no. of faces
The number of ‘faces’ corresponds to the number of regions enclosed by the edges and must include the infinite exterior region.
This formula takes exactly the same form as Euler’s Polyhedron Formula.
An example of two seemingly unrelated areas of mathematics being closely related!
V = 4
E = 6
F = 4
and 4 - 6 + 4 = 2