Maximal Connected Subgraphs

Components as Maximal Connected Subgraphs

Connectedness groups vertices according to whether paths join them. A component is one such group together with the graph structure on it. This tutorial characterizes components in a second way: they are precisely the connected subgraphs that cannot be enlarged while staying connected. The word maximal refers to inclusion, not to having the greatest number of vertices.

Throughout, graphs are finite and simple. A subgraph \(H\) of \(G\) has \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\), with every edge of \(H\) having both endpoints in \(V(H)\). A path joins two vertices when its first and last vertices are those vertices. A graph is connected if it has at least one vertex and every pair of its vertices is joined by a path; a graph with one vertex is connected. We use the convention that the empty graph has no components.

The path relation is an equivalence relation: each vertex is joined to itself by a path of length zero, reversing a path gives a path in the opposite direction, and joining paths gives a walk from which a path can be obtained. Thus the equivalence classes partition \(V(G)\). A component is the induced subgraph on one class, not merely the class as a set of vertices.

The Characterization

Proof. First suppose \(H\) is a component, and let \(C=V(H)\) be its vertex set, an equivalence class of the path relation. The subgraph \(H=G[C]\) is connected: for any \(u,v\in C\), the definition of the class gives a path from \(u\) to \(v\), and every vertex on that path is itself joined to \(u\), so it also lies in \(C\). The path therefore lies in \(G[C]\).

Now suppose a connected subgraph \(J\) of \(G\) contains \(H\). Every vertex \(w\in V(J)\) is joined in \(J\) to a vertex of \(C\), since \(J\) is connected and \(C\) is nonempty. Hence \(w\) belongs to the same equivalence class \(C\). So \(V(J)\subseteq C\), and because \(J\) contains \(H\), also \(V(J)=C\). The subgraph \(H=G[C]\) already contains every edge of \(G\) with both endpoints in \(C\). Thus \(J\) cannot add any edge to \(H\), and \(J=H\). This proves that \(H\) is maximal connected.

Conversely, suppose \(H\) is a maximal connected subgraph of \(G\), and choose any vertex \(r\in V(H)\). Let \(C\) be the equivalence class of \(r\). Every vertex of \(H\) is joined to \(r\) by a path in \(H\), so \(V(H)\subseteq C\). The subgraph \(G[C]\) is connected by the argument above and contains \(H\) as a subgraph. Maximality forces \(H=G[C]\), so \(H\) is a component.

Finally, if \(u,v\) lie in one component, its vertex set is some class \(C\), and its edge set is the edge set of \(G[C]\). By the definition of an induced subgraph, every edge of \(G\) with endpoints \(u,v\) belongs to that component. This also shows why a maximal connected subgraph cannot omit an edge between its own vertices: adding the omitted edge would preserve connectedness and make a larger connected subgraph. \(\square\)

The theorem treats “maximal” as a statement about inclusion of subgraphs. A maximal connected subgraph cannot be enlarged, even by adding a single edge. It need not be larger than every other connected subgraph by vertex count. In particular, an isolated vertex is a maximal connected subgraph when no edge joins it to another vertex.

Worked Examples

Why the Edge Condition Matters

Connectedness asks whether paths exist; it does not require a connected subgraph to include every available edge. Maximality is stronger. If an edge of \(G\) has both endpoints in a connected subgraph, adding that edge does not break any existing path or destroy connectedness. Therefore a maximal connected subgraph must include it. This is why the component is \(G[C]\), the induced subgraph on its vertex class, rather than an arbitrary connected subgraph with the same vertices.

The reverse check is useful too. To show that a connected subgraph is a component, it is not enough to show that its vertices are joined by paths. One must also rule out a connected enlargement. The characterization gives two equivalent ways to do this: show that its vertices form an entire path-equivalence class, or show that no connected subgraph of \(G\) properly contains it. For a proposed component, checking that it contains all edges between its vertices is a necessary part of this verification.

Common Pitfall

A common mistake is to call a connected subgraph maximal merely because no new vertex has yet been listed. In the second example, \(H\) has all three vertices \(a,b,c\) from its proposed component, but it omits the edge \(ac\). The incorrect calculation is to count only \(E(H)=\{ab,bc\}\) and conclude that \(H\) is maximal because it already connects its three vertices. The correction is to compare with the edges of \(G\) whose endpoints are in \(V(H)\): those are \(ab,bc,ac\). Since \(ac\notin E(H)\), the strictly larger connected subgraph with edge set \(\{ab,bc,ac\}\) contains \(H\). So \(H\) is not maximal, even before considering the additional vertex \(d\).

Also avoid replacing “maximal” with “largest.” A component may be smaller than another component and still be maximal, because there is no connected enlargement of it inside \(G\). The isolated-vertex component in the third example is the simplest case.