Complete Graphs

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.

Figure 1: a complete graph with 6 vertices.

Figure 1: a complete graph with 6 vertices.

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

  1. List all 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. Remember the binomial coefficient from C2. This will give you the number of combinations of r elements from a set of n members.

{^n}C_r = \left( \!\! \begin{array}{c} n \\ r \end{array} \!\! \right) = \frac{\displaystyle n!}{\displaystyle r!(n-r)!}
The binomial coefficient gives the number of possible combinations.

For this example, n = 6 and r = 2.

 {^6}C_2 = \frac{\displaystyle 6!}{\displaystyle 2!(6-2)!}
 {^6}C_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}}
 {^6}C_2 = {\displaystyle \frac { 6 \times 5}{2} }
 {^6}C_2 = 15
The number of possible pairs in a set with 6 members.

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.