# Number of edges Upper Bound

Given a simple graph with $n$ vertices and $m$ edges, then show: $m \le \binom{n}{2}$.

Obviously the equality holds when the graph is complete, and if you have less edges, then the inequality would intuitively hold. But how to show this rigorously?

## 2 Answers

An edge is uniquely determined by its set of endpoints, which is a subset of the set of vertices of size $2$, of which there are $\binom{n}{2}$. Hence this is an upper bound.

Let $V$ denote the set of vertices in the graph, and write $V = \{v_1, \ldots, v_n \}$.

$$m = \frac12 \sum_{v \in V} d(v) = \frac12\left( d(v_1) + \ldots + d(v_n) \right)$$

Let $v^* \in V$ such that: $d(v^*) \ge d(v), \forall \ v \in V$. Then:

$$m \le \frac12 \left( d(v^*) + \ldots + d(v^*) \right) = \frac{n}2 d(v^*)$$

But since the graph is simple with $n$ vertices, $v^*$ can't be linked to itself in a loop or linked to another vertex more than once. As a result, $d(v^*) \le n - 1$. Therefore:

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