Answer to Question #222059 in Discrete Mathematics for Sach

Question

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

Answer 1

Let us 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. This leaves us with $\frac{n(n-1)}{2}$.