Lesson 10

Below, we show that a graph with a few edges has many connected components.

Theorem. An undirected graph \(G(V,E)\) has at least \(|V|-|E|\) connected components.

Before proving the theorem, let us consider a few examples. In all of them, \(V=\{1,2,3,4,5\}\). By \(c\), we denote the number of connected components.

• If a graph is connected, then \(|E| \ge |V|-1\). Indeed, if \(|E| \le |V|-2\), then, by the theorem, the graph has at least two connected components.


• If \(|E|=0\), then every node forms a connected component, hence there are \(|V|\) connected components.


• When \(|E| \ge |V|-1\) the lower bound given by the theorem is trivial: it says that there must be at least one connected component.

After developing an intuition, we are ready to prove the theorem.

Proof. We use the trick from the proof of the degree sum formula: start with an empty graph, add edges one by one, each time tracking the values of the two parameters in question (\(|V|-|E|\) and the number of connected components). Initially, when \(E = \emptyset\), both parameters are equal to \(|V|\): \(|V|-|E|=|V|-0=|V|\) and each node forms a connected component. Each time when we add a new edge \(\{u,v\}\), the value of \(|V|-|E|\) drops by one, whereas the number of connected components either drops by one or stays the same:

• if \(u\) and \(v\) belong to different connected components, then adding the edge \(\{u, v\}\) merges these two components (and the number of connected components drops by one);


• if \(u\) and \(v\) belong to the same connected component, then adding the edge \(\{u,v\}\) does not change the set of connected components.