Complete Graphs

A complete graph with 6 vertices.

A complete graph is a form of simple graph. Every pair of vertices must be connected by a single edge. Figure 1 shows an example of a complete graph for a set with 6 elements.

A complete graph with n vertices is given the notation K_n.

We may need to find out the total number of edges in this graph.

  1. List all the possible pairs of vertices :
    • AB, AC, AD, AE, AF
    • BC, BD, BE, BF
    • CD, CE, CF
    • DE, DF
    • EF
  2. Count the number of pairs.
  3. Each pair of vertices must have an edge connecting them so the number of pairs is equal to the number of edges.

Of course, with a set that has many more than 6 elements, you probably wouldn’t want to list all possible pairs. Thankfully there is another, easier way to work out the number of edges in a complete graph. We could calculate the (n-1)th triangle number. \sum_{r=1}^{n-1} r. Remember the binomial coefficient (you might have seen this in your Pure or Statistics lessons).

{^n}C_r = \left( \!\! \begin{array}{c} n \\ r \end{array} \!\! \right) = \frac{\displaystyle n!}{\displaystyle r!(n-r)!}

This binomial coefficient will give you the number of combinations of r elements from a set of n members.

For this example n=6 and p=2.

\begin{aligned}{^6}C_2 &= \frac{\displaystyle 6!}{\displaystyle 2!(6-2)!} \\ &= {\displaystyle \frac { 6 \times 5 \times 4 \times 3 \times 2 \times 1}{ 2 \times 1 \times 4 \times 3 \times 2 \times 1}} \\ &= {\displaystyle \frac { 6 \times 5}{2} } \\ &= 15 \end{aligned}

By using either the formula above, or by counting pairs, we see that the total number of possible pairs in the set is 15. This is the same as the total number of edges in the complete graph for that set.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.