How can I prove the maximum number of edges?

Question

On my book it says that the maximum number of edges E, in a simply connected undirected unweighted graph $G(V,E)$ is $\dfrac{|V|(|V|-1)}{2}$.

How can I show that it is true? Thanks!

Answer 1

I will assume for a moment that you meant $\dfrac{|V|(|V| - 1)}{2}$, as it is hard to describe the number of edges by using the number of edges. And this arises naturally, as this is the number of pairs from $|V|$ vertices, i.e. this is ${|V| \choose 2}$. If we had any more, than the graph would not be simple.

Alternatively, you might now know about complete graphs, which have the maximal number of edges for a set of vertices. They have exactly this number of edges. Having any more would force it to be nonsimple, again.

Answer 2

Another way to view this problem is to use the ``Handshaking Lemma''. Viewing the vertices as people and the edges as handshakes, we could ask how many handshakes are possible among $n$ people if every pair of people shakes hands exactly once. Every person can shake hands with the other $n-1$ people in the room. There are not, however, $n(n-1)$ handshakes, since we are counting every handshake exactly twice in this way (this counts Alice shaking Bob's hand as a different handshake than Bob shaking Alice's hand). Thus, $\frac{1}{2}n(n-1)$ gives us the correct count.