Maximum number of edges one can remove in a biconnected graph and still have it be biconnected
up vote
-1
down vote
favorite
Suppose G=(V,E) is a graph that is biconnected that does not have a hamiltonian path. What is the maximum number of edges that we can remove from E and still have the graph be biconnected? Equivalently, what is the minimum number of edges from E we need to add to the vertices of V so that the resulting graph is biconnected? Furthermore, is it that the total number of edges needed to do so is less than 2|V|?
Thanks!
graph-theory connectedness graph-connectivity
asked Nov 26 at 20:24
graphtheory123
42
add a comment |
up vote
-1
down vote
favorite
Suppose G=(V,E) is a graph that is biconnected that does not have a hamiltonian path. What is the maximum number of edges that we can remove from E and still have the graph be biconnected? Equivalently, what is the minimum number of edges from E we need to add to the vertices of V so that the resulting graph is biconnected? Furthermore, is it that the total number of edges needed to do so is less than 2|V|?
Thanks!
graph-theory connectedness graph-connectivity
asked Nov 26 at 20:24
graphtheory123
42
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Suppose G=(V,E) is a graph that is biconnected that does not have a hamiltonian path. What is the maximum number of edges that we can remove from E and still have the graph be biconnected? Equivalently, what is the minimum number of edges from E we need to add to the vertices of V so that the resulting graph is biconnected? Furthermore, is it that the total number of edges needed to do so is less than 2|V|?
Thanks!
graph-theory connectedness graph-connectivity
asked Nov 26 at 20:24
graphtheory123
42
Suppose G=(V,E) is a graph that is biconnected that does not have a hamiltonian path. What is the maximum number of edges that we can remove from E and still have the graph be biconnected? Equivalently, what is the minimum number of edges from E we need to add to the vertices of V so that the resulting graph is biconnected? Furthermore, is it that the total number of edges needed to do so is less than 2|V|?
Thanks!
graph-theory connectedness graph-connectivity
graph-theory connectedness graph-connectivity
asked Nov 26 at 20:24
graphtheory123
42
asked Nov 26 at 20:24
graphtheory123
42
edited Nov 26 at 20:37
asked Nov 26 at 20:24
graphtheory123
42
asked Nov 26 at 20:24
graphtheory123
42
asked Nov 26 at 20:24
graphtheory123
42
42
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36
add a comment |
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3014873%2fmaximum-number-of-edges-one-can-remove-in-a-biconnected-graph-and-still-have-it%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Why are these two different questions equivalent?
– Mike
Nov 26 at 20:28
Meanwhile this question is poorly worded and needs to be rewritten. If $G$ is a cycle you cannot remove any edges, if $G$ is the complete graph $K_n$ on $n$ vertices you can remove $n choose 2 - n$ edges and the graph will be 2-connected, while there is a set $S$ of $n-2$ edges such that removing $S$ from $K_n$ will make the graph not 2-connected anymore.
– Mike
Nov 26 at 20:33
What I mean by equivalent is that knowing one will tell you the other.
– graphtheory123
Nov 26 at 20:36
Also I don't understand your complete graph example. How can 2-n be in the bottom?
– graphtheory123
Nov 26 at 21:36