How can I prove the maximum number of edges?

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.


The expression $\dfrac{|V|(|V| - 1)}{2}$ 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.


Perhaps you could use induction. Every new vertex you add must have enough edges added to connect to each of the other vertices. It would be assumed each of the others are already connected.

Tags:

Graph Theory