# How can I prove the maximum number of edges?

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!

-
It seems there are some unfortunate typos in the question. (1.) The answer should be $\frac{1}{2}|V|(|V|-1)$ and not what you quote. (2.) I haven't heard of the term "simply connected" in the context of a graph, at least not at such an elementary level. It should just be "simple" (or, "simple, connected" but the answer doesn't change). Which book are you following? Are you sure you didn't make any mistakes in writing the question? –  Srivatsan Sep 3 '11 at 13:34
Related(?): math.stackexchange.com/questions/17747/…. –  Srivatsan Sep 3 '11 at 13:35

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.
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.