Question about Proof of Theorem B.2 (CLRS, Appendix B.5, Theorem B.2, (3) => (4))
Consider the following proof for statement "G is connected but if any edge is removed from E, the resulting graph is disconnected" => "G is connected and |E| = |V| - 1
My understanding is that that the claim about the number of edges is demonstrated using the strategy that if A <= B and B >= A then A = B, with the latter part being proved in Exercise B.4-3. However, on line 5 ("Removing an arbitrary edge...") on the proof the claim is that k >= 2 along with explicit comment that "actually k = 2".
The first question is that since we know from the premise (3) that removing any edge will disconnect the graph and furthermore that removing an edge will disconnect the graph in exactly two connected components, why is the proof insisting on the k >= 2 issue? I cannot think of a way to remove an edge in connected graph and create more than 2 connected components. The removal either disconnects it or not.
Why can we not state directly that removing an edge results in 2 connected components with a total |V| - 2 edges, and therefore by adding it back we reach the desired conclusion? If this were the case, this would remove the need to prove the latter statement that |E| >= |V| - 1.