Question

Suppose you want to provide a general expression for the number of edges in a complete graph Kn. Explain how you could provide some examples to help you find a pattern. How can you use the pattern to create a formula?

from MATH-125

Answer 1

A complete graph is a graph such that

• between each pair of distinct edges, there is exactly one edge
• there are no loops.

So,

• the complete graph with 1 vertex has no edges, since loops can't exist.
• the complete graph with 2 vertices has exactly 1 edge, since there is only 1 pair of distinct edges.
• the complete graph with 3 vertices has exactly 3 edges, since there are 3 pairs of distinct edges, which is clear by looking at a triangle. There are only three ways to join the vertices of a triangle.
• the complete graph with 4 vertices has exactly 6 edges, because to find the number of pairs of distinct edges, we shall first take all possible pairs of distinct vertices that can be obtained from 4 vertices. If the vertices are named 1,2,3,4, then the possible number of ways to select pairs of distince numbers from 1,2,3,4 is . So, the number of edges in the graph will be .

From the above examples, especially from the last one, we can derive a general formula.

Let us suppose that the vertices of the complete graph with n vertices are named 1,2,3,...,n-1,n. Then, the possible number of ways to select two distinct numbers from n numbers is .

Therefore, the general expression for the number of edges in the complete graph is .