1
$\begingroup$

This fact seems obvious but I was unsure how to go about proving it very rigorous.

Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition:

If a graph is connected then $|E| \geq n-1$, i.e. it needs at least n-1 edges.

The fact seems simple and maybe obvious but I was unsure how to rigorously prove the implication. Maybe contrapositive?

The issue that I have with it is that it nearly feels like an axiom. Is there a way to conclude this without assuming it to be true?

$\endgroup$

2 Answers 2

4
$\begingroup$

One way to prove this is by showing that a graph on $n$ vertices with $m$ edges has at least $n-m$ connected components. The proof is by induction on $m$. If $m = 0$ the graph is empty and no vertex is connected to any other. Now suppose that the claim is true for $m$ edges, and consider some graph with $m+1$ edges. Let $C_1,\ldots,C_k$ be its connected components. Choose some arbitrary edge $e = (x,y)$, and suppose that $e \in C_i$. Let $A$ be the set of vertices $v \in C_i$ for which there is a path from $x$ to $v$ not passing through $e$. Any vertex in $C_i \setminus A$ has some simple path to $v$ which passes through $e$. This path ends at $e$, and so there is a path from $y$ to $v$ not passing through $e$. This shows that both $A$ and $C_i \setminus A$ are connected even if we remove $e$. Other connected components are not effected by the removal of $e$ (since $e$ doesn't touch any of their vertices), and so if we remove $e$, the graph has at most $k+1$ connected components. The induction hypothesis shows that $k+1 \geq n-m$, and so $k \geq n-(m+1)$, proving the inductive step.

If a graph is connected then it has one connected component, so $n-m \leq 1$, that is, $m \geq n-1$.

$\endgroup$
3
$\begingroup$

A simple proof. Starting from n vertices with no edges, we add the edges one by one in an arbitrary order. Since adding one edge reduces the number of components by at most one, a graph with less than n-1 edges cannot be connected.

$\endgroup$
1
  • $\begingroup$ That is also my proof, but you haven't proved "very rigorously" that adding an edge reduces the number of components by at most one. $\endgroup$ Commented Oct 3, 2014 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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