Tuesday, July 19, 2005 - 10:54 PM

Here I will show you how to compute the number of edges in a complete graph with n vertices.

What is a complete graph? Well, all three graphs in the following image are complete graphs:


In short a complete graph is one where every vertex is connected to every other vertex.

In the image above, let n represent the number of vertices in the graph (the black dots) and m be the number of edges (the red lines). As you can see, there exists a pattern between the number of vertices and the number of edges. This relation ship can be described by 2m=n(n-1)

Let's do an example. Suppose someone asked you, how many edges does a complete graph with 7 vertices have?

This is a perfect opportunity to apply the formula. Since the graph has 7 vertices, that means that n=7.
So 2m=7*(7-1)
2m=7*6
m=7*3
m=21

Therefore, this graph has 21 edges, as shown in the image below: