Connected Graphs Need at Least n−1 Edges

The Edge Minimum Forced by Connectedness

Connectedness imposes a basic cost: as a graph grows from one vertex to all of its vertices, each newly reached vertex must have an edge linking it to what has already been reached. This gives a lower bound on the total number of edges. It is a necessary condition for connectedness, not a test that by itself guarantees a graph is connected.

Throughout, graphs are finite and simple. A graph \(G=(V,E)\) is connected if every pair of vertices can be joined by a path. We consider connected graphs with \(n=|V|\ge 1\). For a set \(S\subseteq V\), an edge crosses from \(S\) to \(V\setminus S\) if one endpoint is in \(S\) and the other is outside \(S\). A vertex set is connected when the subgraph it induces is connected; a one-vertex set is connected.

The argument does not require that every edge be used. It selects just enough edges to bring in the vertices one at a time. Each selected edge is counted once, when its new endpoint is added.

Finding an Edge Across Every Proper Split

Proof. First suppose \(G\) is connected, and let \(S\) be nonempty and proper. Choose \(x\in S\) and \(y\in V\setminus S\). A path from \(x\) to \(y\) exists by connectedness. As the path starts in \(S\) and ends outside \(S\), some consecutive pair on it has one vertex in \(S\) and one outside. The edge joining that pair crosses the split.

Conversely, suppose every nonempty proper subset has a crossing edge. If \(G\) were disconnected, take the vertex set \(S\) of one connected component. This set is nonempty and proper, because there is at least one other component. No edge can join \(S\) to its complement: such an edge would connect its endpoints and place them in the same component. This contradicts the assumed crossing-edge condition. Therefore \(G\) is connected. \(\square\)

The lemma gives the step needed for the construction. Whenever the vertices reached so far form a nonempty proper subset, connectedness supplies an edge from that set to an unreached vertex. Adding the new endpoint enlarges the reached set by exactly one vertex.

The Lower Bound

Proof. Let \(G=(V,E)\) be connected and choose any starting vertex \(v_1\). Set \(S_1=\{v_1\}\). We build sets \(S_k\) of \(k\) vertices and selected edge sets \(F_k\subseteq E\), beginning with \(F_1=\varnothing\).

Suppose \(1\le k<n\), and \(S_k\) has already been built. It is nonempty and proper, so the lemma gives an edge \(e_k=x_ky_k\) with \(x_k\in S_k\) and \(y_k\notin S_k\). Define \(S_{k+1}=S_k\cup\{y_k\}\) and \(F_{k+1}=F_k\cup\{e_k\}\). The new set has \(k+1\) vertices. Also, \(e_k\) is not an edge previously selected: both endpoints of every earlier selected edge lie in the current set \(S_k\), whereas \(y_k\) is outside it. Thus each step adds one distinct edge. By induction, \(|F_k|=k-1\) for every \(1\le k\le n\).

At the end, \(S_n=V\), so \(F_n\) is a subset of the graph's edge set \(E\). Consequently, \[ |E|\ge |F_n|=n-1. \] If \(n=1\), there are no construction steps and \(F_1=\varnothing\); the same inequality reads \(|E|\ge 0\), which holds. This covers the one-vertex case as well. \(\square\)

The construction selects exactly \(n-1\) edges, one for each addition after the initial vertex. It does not claim that these are all the edges of the graph. Additional edges may join vertices already reached without being needed to expand the set.

Worked Counts

What the Bound Does—and Does Not—Say

The theorem is a necessary condition: if a graph is connected, then \(m\ge n-1\). Its contrapositive is useful too: if a graph on \(n\ge1\) vertices has fewer than \(n-1\) edges, then it cannot be connected. But the bound alone does not certify connectedness. A graph may have at least \(n-1\) edges and still be disconnected, for example if some of its edges are concentrated in one part while another vertex is isolated.

At equality, the construction uses as many edges as the graph has, as in the first and third examples. If there are more than \(n-1\) edges, the construction still selects \(n-1\) distinct edges, and the other edges are simply not required by that particular growth process. The lower-bound proof does not need to classify all graphs that attain equality.

This counting argument is useful when checking proposed edge lists, designing networks that must connect a specified number of locations, and understanding why a graph with very few edges cannot keep all its vertices connected. It also explains the number \(n-1\) structurally: there is one initial vertex, then \(n-1\) further vertices, each of which needs a selected link to the vertices already reached.

Common Counting Pitfall

A common mistake is to count incident edges as though every vertex required its own distinct edge. For example, let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). This graph is connected and has \(n=4\), \(m=3\). The incorrect claim “each of the four vertices needs an incident edge, so at least four edges are needed” counts vertices, not distinct edges. An edge can be incident to two vertices: here the four vertices are incident to the three edges, with the middle edges \(23\) touching two vertices each.

The correct argument does not assign a separate edge to every vertex. It fixes one starting vertex and selects one new edge for each of the other \(n-1\) vertices as they are added. In this example, start at \(1\), then add \(2\) along \(12\), \(3\) along \(23\), and \(4\) along \(34\). There are three additions and three distinct selected edges, exactly matching \(n-1=4-1=3\).