Could a graph with $n>1$ vertices and $m<n-1$ edges be connected?

Question

It's easy to verify (with some n's) that's true but how can I formalize a proof to answer this question? Any hint?

Answer 1

Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.

---

Definition: a connected component $A$ of the graph is a set of nodes such that

• a path exists between any two nodes in $A$, and
• $A$ is not a proper subset of any other set of nodes for which such a path exists.

Note that by this definition, an isolated node is also a connected component.

Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.

Now consider what happens each time we add an edge.

There are two possibilities:

• The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
• The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.

Therefore each edge added reduces the number of components by at most $1$.

In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is

$$c\ge n-k.$$

For $G$ to be connected we require $c=1$, so this becomes

$$1\ge n-k,$$

and therefore

$$k\ge n-1.$$

That is, a connected graph with $n$ nodes has at least $n-1$ edges.