Two Different Questions About Connectivity
Connectivity can be minimal in one sense and maximal in another. To test whether a connected graph is minimal, hold its vertex set fixed and ask whether any edge can be removed without disconnecting it. To test whether a connected subgraph is maximal, hold the host graph fixed and ask whether it can be enlarged while remaining connected. The first is about removing edges; the second is about enlarging a subgraph.
All graphs below are finite and simple. A graph is connected if it is nonempty and every pair of its vertices is joined by a path; a single-vertex graph is connected. A subgraph \(H\) of \(G\) has \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\), with every edge in \(E(H)\) having both endpoints in \(V(H)\). A subgraph need not be induced: it may omit some edges of \(G\) whose endpoints it includes.
Minimality is tested by deleting edges, not vertices. Maximality is tested by enlarging a subgraph within a specified host graph. Neither word means simply “small” or “large.” A further term, maximum, refers to a subgraph attaining the largest value of a specified measure, such as number of vertices. A maximal subgraph need not be maximum.
Minimal Connectedness and Trees
A tree is a connected acyclic graph. The earlier result on minimal connectivity identifies trees with minimally connected graphs. Here is the short argument that explains why edge deletion is the relevant test.
Proof. Suppose first that \(G\) is minimally connected. If \(G\) contained a cycle, choose an edge \(e=uv\) on that cycle. The rest of the cycle gives a path from \(u\) to \(v\) that avoids \(e\). Any path in \(G\) that uses \(e\) can therefore replace that edge by the alternate path, producing a walk with the same endpoints that avoids \(e\). Removing repeated sections of a walk gives a path, so every pair of vertices remains connected in \(G-e\). This contradicts minimal connectivity. Thus \(G\) is acyclic as well as connected, so it is a tree.
Conversely, suppose \(G\) is a tree. It is connected. If some edge \(e=uv\) could be deleted while leaving \(G-e\) connected, there would be a \(u\)-\(v\) path in \(G-e\). That path together with \(e\) would form a cycle in \(G\), contrary to acyclicity. Therefore deleting any edge disconnects \(G\), and \(G\) is minimally connected. If \(G\) has one vertex, it has no edges, so the edge-deletion condition is vacuous; it is connected and acyclic, hence a tree. \(\square\)
This characterization concerns a connected graph on its existing vertices. It does not say that a minimally connected graph is a maximal connected subgraph of every graph containing it, or that a maximal connected subgraph is minimally connected.
Worked Example: A Minimally Connected Path
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34\}\). It is the path \(P_4\). It is connected: the listed edges join \(1\) to \(2\), \(2\) to \(3\), and \(3\) to \(4\), so the sequence \(1,2,3,4\) joins the endpoints, and its subsequences join each other pair.
Test deletion of each edge. Deleting \(12\) leaves \(V=\{1,2,3,4\}\) and \(E=\{23,34\}\); vertex \(1\) is isolated, so the result is disconnected. Deleting \(23\) leaves \(E=\{12,34\}\), which has two components. Deleting \(34\) leaves \(E=\{12,23\}\); vertex \(4\) is isolated. Each deletion disconnects the graph, so \(G\) is minimally connected.
Check: The order is \(n=4\) and the size is \(m=3\), so \(m=n-1=4-1=3\). This count agrees with the earlier tree characterization for connected graphs with \(n-1\) edges. It is a check here, while the edge-deletion test directly verifies minimal connectivity.
Maximal Connected Subgraphs Are Components
A connected component is a maximal connected part of a graph. Its maximality is relative to the host graph: it cannot be enlarged into a larger connected subgraph using vertices and edges of that host graph.
Proof. Let \(H\) be a maximal connected subgraph of \(G\), and choose a vertex \(v\in V(H)\). Let \(C\) be the component containing \(v\), meaning the set of all vertices that can be reached from \(v\) by paths in \(G\), together with all edges of \(G\) whose endpoints are in that set. Since \(H\) is connected, each of its vertices is reachable from \(v\), so \(H\) is contained in \(C\). The component \(C\) is connected and is a subgraph of \(G\); maximality of \(H\) therefore implies \(H=C\).
For the other direction, let \(C\) be a component and suppose a connected subgraph \(J\) of \(G\) contains \(C\). If \(J\) contained a vertex outside \(C\), a path in \(J\) from a vertex of \(C\) to that outside vertex would connect it to \(C\) in \(G\), contradicting the definition of the component. Thus \(J\) has no vertices outside \(C\). All edges of \(G\) with endpoints in \(C\) are already included in the component, so \(J\) cannot properly enlarge \(C\). Hence \(C\) is maximal connected in \(G\). If \(G\) is connected, it has one component, namely \(G\). \(\square\)
The empty graph has no connected components under our convention that a connected graph is nonempty; correspondingly, it has no maximal connected subgraphs. In a disconnected graph, each component is maximal, but some components can be smaller than others. If “maximum” means greatest order, only a component of largest vertex count is maximum by order.
Worked Example: A Maximal Component That Is Not Maximum
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,23,13,45,46,47,56,57,67\}\). The vertices \(\{1,2,3\}\) form a triangle, and \(\{4,5,6,7\}\) form a complete graph \(K_4\). There are no edges between these sets, so they are the two connected components.
The triangle on \(\{1,2,3\}\) is maximal connected: no connected supergraph of it within \(G\) can add a vertex from \(\{4,5,6,7\}\), because there is no edge joining the triangle’s component to that other component. The \(K_4\) is maximal connected for the same reason. Their orders are \(3\) and \(4\), respectively, so the triangle is maximal but is not maximum by order. The \(K_4\) is maximum by order, since \(4>3\).
Check: The triangle contributes the three edges \(12,23,13\), and \(K_4\) contributes the six edges \(45,46,47,56,57,67\). Thus the graph has \(3+6=9\) edges, and all nine are within the two separate components. The absence of a crossing edge confirms that the components cannot be combined into a larger connected subgraph.
Examples That Separate the Tests
Worked Example: Connected but Not Minimally Connected
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34,41\}\), a 4-cycle. The graph is connected: its cycle gives a route between each pair of vertices. But deleting edge \(12\) leaves the path with edge set \(\{23,34,41\}\), which still joins all four vertices. Hence \(G\) is not minimally connected. It has a cycle, and the alternate route \(1,4,3,2\) replaces the deleted edge.
As a subgraph of itself, \(G\) is maximal connected in \(G\): there is no larger subgraph of \(G\) containing it. This does not make it minimally connected. The example has \(n=4\) and \(m=4\), so \(m=4\) is not \(n-1=3\), consistent with the earlier characterization that a connected graph with \(n-1\) edges is a tree.
Check: The two tests give different answers. Edge deletion shows that \(G\) is not minimal; inclusion in the host graph shows that \(G\) is maximal connected there.
Worked Example: A Component That Is Not Minimally Connected
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,13\}\). Vertex \(4\) is isolated, and \(\{1,2,3\}\) is a triangle. The triangle is a maximal connected subgraph of \(G\): the only vertex outside it is \(4\), and no edge joins \(4\) to the triangle.
However, the triangle is not minimally connected. Deleting edge \(12\) leaves edges \(\{23,13\}\), which still connect all three triangle vertices by the path \(2,3,1\). Deleting \(23\) leaves \(\{12,13\}\), and deleting \(13\) leaves \(\{12,23\}\); each remaining pair of edges is a path through all three vertices. Thus none of the three edge deletions disconnects the triangle. The isolated-vertex component \(\{4\}\), by contrast, is a one-vertex tree and is minimally connected under the stated definition.
Check: The graph has \(n=4\) vertices and \(m=3\) edges, but it is disconnected, so the connected-graph edge-count test cannot be used to call the whole graph a tree. The component orders are \(3\) and \(1\); the triangle is the maximum component by order, although it is not minimally connected.
Common Pitfalls
Confusing maximal with maximum. Maximal means that no proper enlargement of the specified kind is possible. Maximum means largest according to a specified measure. In the seven-vertex example, the triangle is maximal connected but not maximum by order because it has \(3\) vertices while the \(K_4\) component has \(4\).
Adding a vertex without connecting it. A tempting but incorrect argument is: “The triangle component can be enlarged by adding isolated vertex \(4\), so it is not maximal.” Adding \(4\) alone gives a subgraph with two components, not a connected supergraph of the triangle. In the definition of maximal connected, only connected enlargements count. As the component theorem shows, a vertex outside the component cannot be added while preserving connectivity in the host graph.
Checking the wrong operation. To test minimal connectivity, delete each edge while retaining the vertices. To test maximal connectedness, look for a larger connected subgraph of the host graph. A graph can pass one test and fail the other: a tree is minimally connected, and if it is itself the host graph it is also maximal connected there; a cycle is maximal connected in itself but not minimally connected.
Check Your Understanding
For each question, keep the host graph and the relevant test explicit.
- Let \(G\) have \(V=\{a,b,c\}\) and \(E=\{ab,bc\}\). Is \(G\) minimally connected? Check each edge deletion.
- Let \(G\) consist of two disjoint triangles. How many maximal connected subgraphs does it have, and are they both maximum by order?
- Explain why adding an isolated vertex to a connected subgraph does not produce a connected supergraph.
- Give an example of a maximal connected subgraph that is not minimally connected, and verify both claims.
- Why does the edge-deletion condition for minimal connectivity hold vacuously for a one-vertex graph, and why does that graph still satisfy the definition?