When Is a Connected Graph Minimal?
A connected graph may contain edges that are unnecessary for keeping its vertices connected. If removing one edge leaves the graph connected, that edge can be discarded without losing connectivity. A tree has no such redundant edge: removing any edge disconnects it. This gives a characterization of trees in terms of minimal connectedness, rather than in terms of cycles or edge counts alone.
Throughout, graphs are finite and simple. A graph \(G=(V,E)\) is connected if it is nonempty and every pair of vertices is joined by a path. A tree is a connected graph with no cycles. For an edge \(e\), the graph \(G-e\) has vertex set \(V(G)\) and edge set \(E(G)\setminus\{e\}\). Thus deleting an edge never deletes its endpoints. A graph with one vertex and no edges is connected; the condition that deleting any edge disconnects it holds vacuously because it has no edges.
A spanning subgraph of \(G\) has the same vertex set as \(G\) and an edge set contained in \(E(G)\). The definition concerns whether any edges can be removed while preserving connectedness; it does not compare \(G\) with graphs on different vertex sets.
What Happens When One Edge Is Deleted?
Fix an edge \(e=uv\) of a connected graph. The key question is whether \(u\) and \(v\) are still joined after \(e\) is deleted. If they are, the edge was not needed: any route that used \(e\) can instead travel between \(u\) and \(v\) along another path. If they are not, deleting \(e\) separates the graph.
Proof. If \(G-e\) is connected, then its vertices \(u\) and \(v\) are joined by a path. Conversely, suppose \(G-e\) contains a \(u\)-\(v\) path. Take any two vertices \(x,y\). Since \(G\) is connected, there is an \(x\)-\(y\) path in \(G\). If it does not use \(e\), it remains a path in \(G-e\). If it does use \(e\), replace that use of \(e\) by the \(u\)-\(v\) path in \(G-e\). This gives an \(x\)-\(y\) walk in \(G-e\), and deleting any repeated portions of a walk gives a path with the same endpoints. Thus \(G-e\) is connected.
It remains to relate this to a cycle. If there is a \(u\)-\(v\) path in \(G-e\), that path together with \(e\) forms a cycle: the path has no repeated vertices, and it cannot have length \(1\), since \(G\) is simple and \(e\) is the only edge between \(u\) and \(v\). Conversely, if \(e\) belongs to a cycle, the rest of that cycle is a \(u\)-\(v\) path in \(G-e\). The two conditions are therefore equivalent. \(\square\)
The Characterization of Trees
Proof. Let \(G\) be connected. If \(G\) is a tree, it has no cycles. By the lemma, if deleting an edge \(e\) left \(G-e\) connected, then \(e\) would belong to a cycle of \(G\). That is impossible, so deleting every edge disconnects \(G\).
Conversely, suppose deleting every edge disconnects \(G\). If \(G\) had a cycle, choose any edge \(e\) on that cycle. The rest of the cycle would provide a path between the endpoints of \(e\) after \(e\) was deleted. The lemma would then imply that \(G-e\) is connected, contrary to the assumption. Therefore \(G\) has no cycles. Since \(G\) is connected and acyclic, it is a tree. If \(G\) has one vertex, it has no edges and no cycles, so it is a tree and the edge-deletion condition is vacuously true. \(\square\)
The theorem says more than “trees have few edges.” It identifies exactly what makes their connectedness minimal: every edge is necessary. In the earlier material on connected graphs and edge counts, a connected graph of order \(n\) was shown to have at least \(n-1\) edges, and a connected graph with \(n-1\) edges was shown to be a tree. Those counts are useful, but the deletion test asks a different, local question: does removing each particular edge destroy connectivity?
Worked Example: Testing Every Edge of a Path
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,34,45\}\). This is the path \(1,2,3,4,5\). It is connected because consecutive edges give a path between any two of its vertices.
Delete the edges one at a time. The resulting components are:
- After deleting \(12\), the components have vertex sets \(\{1\}\) and \(\{2,3,4,5\}\).
- After deleting \(23\), the components have vertex sets \(\{1,2\}\) and \(\{3,4,5\}\).
- After deleting \(34\), the components have vertex sets \(\{1,2,3\}\) and \(\{4,5\}\).
- After deleting \(45\), the components have vertex sets \(\{1,2,3,4\}\) and \(\{5\}\).
In each case there are exactly two components, so every edge deletion disconnects the graph. The theorem confirms that \(G\) is a tree. As a separate numerical check, its order is \(5\) and its size is \(4\), so \(|E(G)|=4=5-1\), consistent with the edge count for a tree.
Check: Before deletion the graph has \(4\) edges; after each listed deletion it has \(3\) edges and the listed two components. In particular, the edge count agrees with the component descriptions, but the component descriptions—not the count alone—verify that each deletion disconnects.
Worked Example: A Cycle Edge Is Redundant
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,31,34\}\). The vertices \(1,2,3\) form a triangle, and vertex \(4\) is joined to \(3\). The graph is connected.
Check all four edge deletions. If \(12\) is deleted, the remaining edges \(23,31,34\) still connect all vertices by the route \(1,3,2\), with \(4\) attached at \(3\). If \(23\) is deleted, the remaining edges \(12,31,34\) connect all vertices by \(2,1,3,4\). If \(31\) is deleted, the remaining edges \(12,23,34\) connect all vertices by \(1,2,3,4\). Thus each of the first three deletions leaves a connected graph.
If \(34\) is deleted, the remaining edges \(12,23,31\) connect \(\{1,2,3\}\), while vertex \(4\) has no incident edge. The components have vertex sets \(\{1,2,3\}\) and \(\{4\}\), so this deletion disconnects the graph. Since deleting \(12\), for example, preserves connectivity, \(G\) is not edge-minimal connected and is not a tree. The reason is that edge \(12\) lies on the cycle \(1,2,3,1\).
Check: The original graph has \(4\) edges. Deleting any one of \(12,23,31\) leaves \(3\) edges and a connected graph; deleting \(34\) also leaves \(3\) edges but gives \(2\) components. The same edge count after deletion does not determine whether connectivity remains.
Edge-Minimal Connected Graphs
Proof. Suppose \(G\) is edge-minimal connected and \(H\) is a connected spanning subgraph of \(G\). If \(H\) were proper, it would omit at least one edge \(e\in E(G)\). Then \(H\) would be a connected spanning subgraph of \(G-e\), which would force \(G-e\) to be connected. This contradicts edge-minimality. Hence \(G\) has no proper connected spanning subgraph.
Conversely, suppose \(G\) has no proper connected spanning subgraph. For any \(e\in E(G)\), the graph \(G-e\) is a proper spanning subgraph. It cannot be connected by the supposition, so deleting any edge disconnects \(G\). Therefore \(G\) is edge-minimal connected. \(\square\)
Combining the proposition with the theorem gives an equivalent description: among connected graphs on a fixed vertex set, the edge-minimal ones are exactly the trees. This is an inclusion-minimal condition on edges. For a connected graph of fixed order, the edge-count results mentioned above also imply that a tree has the minimum possible number of edges, namely \(n-1\). The deletion characterization and the edge count express related facts in different ways: one checks individual edges, while the other counts all edges.
Worked Example: The Same Edge Count, Different Connectivity
Consider two graphs on the same vertex set \(\{1,2,3,4\}\). Let \(P\) have edge set \(\{12,23,34\}\), and let \(H\) have edge set \(\{12,23,31\}\). Both graphs have \(3\) edges, and \(3=4-1\).
For \(P\), the edge list forms the path \(1,2,3,4\), so \(P\) is connected. Deleting \(12\) separates \(\{1\}\) from \(\{2,3,4\}\); deleting \(23\) separates \(\{1,2\}\) from \(\{3,4\}\); deleting \(34\) separates \(\{1,2,3\}\) from \(\{4\}\). Thus \(P\) is edge-minimal connected and, by the theorem, a tree.
For \(H\), the edges connect \(1,2,3\) in a triangle, but vertex \(4\) is isolated. Therefore \(H\) has two components and is not connected. Its \(3\) edges do not make it a tree or an edge-minimal connected graph.
Check: In each graph the edge count is \(3\), obtained by counting the displayed edge set. But \(P\) has one component and \(H\) has two. An edge count by itself does not establish the connectedness required in the tree characterization.
A Common Mistake
A tempting but incorrect argument is: “There are four vertices and three edges, so the graph is a tree.” This calculation checks only that \(m=n-1\). It omits the necessary condition that the graph be connected. In the preceding example, \(H\) has \(n=4\) vertices and \(m=3\) edges, but vertex \(4\) is isolated, so \(H\) is disconnected and is not a tree.
The correction is to use the hypotheses of the result being applied. The theorem “a connected graph with \(n-1\) edges is a tree” requires connectedness. For the minimal-connectivity test, first verify that the original graph is connected, then delete each edge and check whether the resulting graph is disconnected. Finding one edge whose deletion leaves the graph connected is enough to show that the graph is not edge-minimal connected; confirming the property requires checking every edge.
This viewpoint is useful when a graph is given by its edge list and the question is whether all its links are essential. It also separates two different failures: a graph may fail to be connected before any deletion, or it may be connected but contain an edge whose deletion preserves connectivity. Only a connected graph for which every edge is necessary is a tree.
Check Your Understanding
For each question, use the edge-deletion criterion and state any connectivity assumption you need.
- Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,cd\}\). List the components after deleting \(bc\), and decide whether \(G\) is edge-minimal connected.
- Suppose \(G\) is connected and an edge \(uv\) lies on a cycle. Explain why deleting \(uv\) leaves \(G\) connected.
- Can a disconnected graph satisfy “deleting every edge disconnects the graph” while still not being a tree? Give an example and explain the role of the connectedness hypothesis.
- Explain why a connected graph with an edge whose deletion leaves it connected cannot be a tree.
- For a connected graph with one vertex and no edges, does the condition “deleting every edge disconnects the graph” hold? Explain why this case does not contradict the theorem.