Problem
COM-B2-M04-P006 A Connected Graph and a Tree
Prove that from every finite connected graph one can remove some edges so that the graph remains connected and contains no cycles.
Among connected spanning subgraphs, choose one with the fewest edges.
Consider all connected subgraphs containing all vertices of the original graph. Choose one, \(H\), with the smallest number of edges. It exists because the original graph is among them.
If \(H\) contains a cycle, remove one edge of that cycle. Its endpoints are still connected through the rest of the cycle, so connectivity is preserved. This gives a connected spanning subgraph with fewer edges, a contradiction.
Thus \(H\) has no cycles. The desired graph is obtained by deleting redundant edges.
This is essentially a proof of the existence of a spanning tree.