3
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – NasuSama Mar 30 '14 at 23:39
  • $\begingroup$ 0oo, I didn't know I could use MathJax in titles too. thanks for the fix and teaching me something new $\endgroup$ – audiFanatic Mar 30 '14 at 23:41
  • $\begingroup$ 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" $\endgroup$ – audiFanatic Mar 30 '14 at 23:43
5
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.