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

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.

• You need to show that this is true for any simple graph. You only gave the example that the statement holds. I believe the best start is to prove by contradiction. – NasuSama Mar 30 '14 at 23:39
• 0oo, I didn't know I could use MathJax in titles too. thanks for the fix and teaching me something new – audiFanatic Mar 30 '14 at 23:41
• exactly, that's what I'm not sure about. I can show that the other extreme is true as well by removing any $3$ edges. Removing any more than that makes the graph disconnected and the inequality would fail. However, I'm not exactly sure that showing this for the extreme cases would be considered a "proof" – audiFanatic Mar 30 '14 at 23:43

• 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$
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}$.