Prove for a simple graph that $n-1 \leq m \leq \frac{n(n-1)}{2}$

Question

For a given simple (that is neither loops nor multiple edges are allowed) undirected graph, where $m$ is the number of edges and $n$ is the number of vertices that the following inequality holds.

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

---

Now, I have proved this myself, but I'm not sure that it would be considered a "formal", rigorous proof.

Basically I said the following. Consider a complete graph, we have the extreme case where every node is connected to eachother. So supposing we have the complete graph $K_4$ as shown below, then this should be the extreme case and the inequality is satisfied, there the middle and right-most terms are equal. Therefore the inequality should hold for less extreme simple graphs as well.

Answer 1

Hint:

• Inequality $n-1 \leq m$ works only for connected graphs (e.g. consider a graph with two vertices and no edges). For connected graphs, I would suggest induction (there are similar questions already).
• Inequality $m \leq \frac{n(n-1)}{2}$ could be rewritten as $m \leq \binom{n}{2}$. Use the fact that edges are undirected pairs.

I hope this helps $\ddot\smile$

Answer 2

Your statement is true only for connected graphs. An extreme example would be the empty graph on $n$ vertices with $m=0$.

A minimally connected graph on $n$ vertices is a tree. A tree has exactly $n-1$ edges. There are all kinds of ways to characterize this and prove this.

A maximally connected graph on $n$ vertices is $K_n$. $K_n$ has exactly $\binom{n}{2}=\frac{n(n-1)}{2}$.