Let $G$ be a simple graph. Show that $m\leq {n \choose 2}$, and determine when equality holds.

Question

I'm reading Bondy and Murthy's Graph Theory, and I'm doing the proposed exercise in the title. I've tried to do the following:

$m$: Edges

$n$: Vertices

A simple graph with $n$ vertices has a maximum of $m=(n-1)+(n-2)+\dots+(n-n)$ and hence

$$m=(n-1)n-\frac{(n-1)(n)}{2}=\frac{n^2-n}{2}$$

Which is $(n-1)$ times the number of $n$'s and the sum of the first $(n-1)$ natural numbers. Knowing that the maximum number of edges in a simple graph is ${n \choose 2}$, we can write:

$$\begin{eqnarray*} {m}&\leq&{{n \choose 2}}\\ {}&&{}\\ {\frac{n^2-n}{2}}&\leq&{\frac{n!}{2(n-2)}}\\ {}&&{}\\ {n^2-n}&\leq&{\frac{n!}{(n-2)!}}\\ {}&&{}\\ {n^2-n}&\leq&{n \cdot (n-1)}\\ {}&&{}\\ {n^2-n}&\leq&{n^2-n}\\ {}&&{}\\ {n^2-n}&\leq&{n^2-n} \end{eqnarray*}$$

Answer 1

Assume that $m\gt{n\choose 2}$ where the order and size of $G$ is $n$ and $m$, respectively. We know that $K_n$ has exactly ${n\choose 2}$ edges. Since $m\gt{n\choose 2}$ this implies that $G$ contains at least $1$ multiple edge which contradicts the fact that $G$ is simple. Thus for all simple graphs $G$ we know that $m\leq {n\choose 2}$.

Answer 2

An edge in a simple graph can be thought of as a set of two vertices (its end points), there is $ {n \choose 2} $ sets of size two from the set of vertices. If $X$ is the set of vertex subsets of size 2 then the edge set $E$ is a subset of $X$ so $m = |E| \leq |X| = {n \choose 2} $