2
$\begingroup$

Given a graph $G = (V,E)$, prove that if $G$ connected and $G$ becomes disconnected after removing any edge, then $G$ is a tree .

For this proof I would only like to ask on the contrapositive proof given by my Professor. So basically I am proving if $G$ is not a tree, then $G$ is either not connected or $G$ is still connected after removing any edge.

So if $G$ is not a tree, then he said if $G$ has a cycle , removing an edge in the cycle still makes the graph connected. This i completely understand, but the questions says any edge, so what if $G$ is connected but we remove an edge not from the cycle? Does it not make the $G$ disconnected still...? Am I missing something?

$\endgroup$
2
$\begingroup$

If we rewrite the original assertion as 'if for all edges, removing them from $G$ gives a connected graph, then $G$ is a tree', from here it is clear that the contrapositive is: 'if $G$ is not a tree, there exists an edge for which $G$ will remain connected when removing it'. So you can choose which edge to remove, as long as it makes $G$ to remain connected.

$\endgroup$
1
  • $\begingroup$ Understood, so I interpret the contrapositive wrongly. Thanks! $\endgroup$
    – nan
    Sep 8 '18 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.