A Taste of University Mathematics
Graph Theory is a thriving area of modern mathematics
At school, we learn about co-ordinates and graphs. You might be familiar with graphs of functions such as y = 2x -1 or y = sin x
​
In higher mathematics, Graph Theory is a completely separate area of study that has nothing to do with the graphs we meet at school and college.
​
Graph Theory is one of the most lively areas of current mathematical research and contains some important unsolved problems such as the Travelling Salesman Problem.
​
So lets look at some Graph Theory.
​
A graph drawing is made up of vertices and edges as shown below:
The red dots are the vertices and the black lines are the edges.
The graph drawing above has 4 vertices and some of the vertices are connected by edges.
​
The degree of each vertex is the number of edges that meet at that vertex.
​
In our graph drawing, two of the vertices (numbers 2 and 4) have degree 2 and the other two vertices (numbers 1 and 3 ) have degree 3.
​
Challenge 1
Can you draw three vertices on a piece of paper and connect each vertex to every other vertex exactly once?
​
None of the edges are allowed to cross.
Hopefully you managed that challenge!
You could do it in many ways. Two examples are shown below.
Notice that however we draw the diagram, it will always have exactly three edges. Remember that we could have put the vertices anywhere on the paper.
​
A graph drawing in which each vertex is joined to every other vertex is called complete.
A complete graph of size ’n’ is denoted by Kn where ‘n’ is the number of vertices.
The graph drawings above are examples of the complete graph called K3 . Note that the edges do not have to be straight but they can be if we so choose.
​
We can draw Kn for any number of vertices.
“It is thought that the letter K stands for the German word ‘Komplett’ meaning complete.”
Challenge 2
Can you draw the graph diagram of the complete graph K4?
​
None of the edges are allowed to cross.
If you were successful in drawing K4 without any edges crossing, you should have ended up with a total of 6 separate edges in your graph drawing.
​
This is because each of the 4 vertices has 3 edges emerging from it and 4 x 3 = 12.
​
However, notice that in calculating 4 x 3, we have counted each edge twice. Check this by carefully counting each edge in your drawing of K4.
3 edges emerge from each vertex to connect with the other 3 vertices.
So the correct way to calculate the number of edges in K4 is to multiply 4 by 3 and then divide the result by 2.
Shown below are two possible ways to draw K4 without any edges crossing
There are an infinite number of ways of drawing K4 with no edges crossing.
“The study of Graph Theory was heavily influenced by Leonhard Euler”
​
For any complete graph Kn, the number of edges (e) is given by the formula below where ‘n’ stands for the number of vertices.
​
This formula is true for any size of complete graph Kn. It works because:
-
There are ‘n’ vertices
​
-
There are ‘n-1’ edges emerging from each vertex so we multiply ‘n’ by ‘n-1’
​
-
Each edge is counted twice so we must divide by two to obtain the correct result
Now that K4 is done with, we can look at K5. We see that it must have 10 edges:
Drawing a graph diagram of K5 is not very difficult or time consuming. An example is shown below.
However, in the drawing of K5 above, notice that there are two edges that cross.
Challenge 3
Can you draw the graph diagram of the complete graph K5?
​
None of the edges are allowed to cross.