Prove that if $G$ connected and $G$ becomes disconnected after removing any edge, then $G$ is a tree .
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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?
graph-theory
asked Sep 8 at 4:56
ilovewt
911317
add a comment |Â
up vote
2
down vote
favorite
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?
graph-theory
asked Sep 8 at 4:56
ilovewt
911317
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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?
graph-theory
asked Sep 8 at 4:56
ilovewt
911317
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?
graph-theory
graph-theory
asked Sep 8 at 4:56
ilovewt
911317
asked Sep 8 at 4:56
ilovewt
911317
edited Sep 8 at 5:02
asked Sep 8 at 4:56
ilovewt
911317
asked Sep 8 at 4:56
ilovewt
911317
asked Sep 8 at 4:56
ilovewt
911317
911317
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Sep 8 at 5:03
Guido A.
4,806728
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Sep 8 at 5:03
Guido A.
4,806728
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
add a comment |Â
up vote
2
down vote
accepted
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.
answered Sep 8 at 5:03
Guido A.
4,806728
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
answered Sep 8 at 5:03
Guido A.
4,806728
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.
answered Sep 8 at 5:03
Guido A.
4,806728
answered Sep 8 at 5:03
Guido A.
4,806728
answered Sep 8 at 5:03
Guido A.
4,806728
answered Sep 8 at 5:03
Guido A.
4,806728
4,806728
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
add a comment |Â
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
Understood, so I interpret the contrapositive wrongly. Thanks!
– ilovewt
Sep 8 at 5:05
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2909282%2fprove-that-if-g-connected-and-g-becomes-disconnected-after-removing-any-edge%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
