Answer to Question #226896 in Discrete Mathematics for Sach

Question

Show that a complete graph with n vertices has
n(n -1) 2
edges

Answer 1

Solution:

We have to show that a complete graph with n vertices has exactly $\frac{n(n-1)}{2}$ edges.

A complete graph means that every vertex is connected with every other vertex.

If we take one vertex of the complete graph, we therefore have $n-1$ outgoing edges from that particular vertex.

Now, we have $n$ vertices in total, so we might be tempted to say that there are $n(n−1)$ edges in total, $n-1$ for every vertex in our graph.

But this method counts every edge twice, because every edge going out from one vertex is an edge going into another vertex.

Hence, we have to divide your result by 2.

We get $\frac{n(n-1)}{2}$.

Hence, proved.