Show that this graph is $k$-connected
up vote
0
down vote
favorite
Given a $k$-connected graph $G$, let $G'$ be a graph obtained from $G$ by adding a new vertex $x$ and connecting it to any $k$ vertices of $G$. From first principles, show that $G'$ is $k$-connected.
I understand visually how this is, just don't know how to "show it from first principles".
graph-theory
asked Nov 19 at 9:57
user499701
1037
add a comment |
up vote
0
down vote
favorite
Given a $k$-connected graph $G$, let $G'$ be a graph obtained from $G$ by adding a new vertex $x$ and connecting it to any $k$ vertices of $G$. From first principles, show that $G'$ is $k$-connected.
I understand visually how this is, just don't know how to "show it from first principles".
graph-theory
asked Nov 19 at 9:57
user499701
1037
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given a $k$-connected graph $G$, let $G'$ be a graph obtained from $G$ by adding a new vertex $x$ and connecting it to any $k$ vertices of $G$. From first principles, show that $G'$ is $k$-connected.
I understand visually how this is, just don't know how to "show it from first principles".
graph-theory
asked Nov 19 at 9:57
user499701
1037
Given a $k$-connected graph $G$, let $G'$ be a graph obtained from $G$ by adding a new vertex $x$ and connecting it to any $k$ vertices of $G$. From first principles, show that $G'$ is $k$-connected.
I understand visually how this is, just don't know how to "show it from first principles".
graph-theory
graph-theory
asked Nov 19 at 9:57
user499701
1037
asked Nov 19 at 9:57
user499701
1037
asked Nov 19 at 9:57
user499701
1037
asked Nov 19 at 9:57
user499701
1037
asked Nov 19 at 9:57
user499701
1037
1037
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11
add a comment |
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.
answered Nov 19 at 10:10
mathnoob
1,247116
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.
answered Nov 19 at 10:10
mathnoob
1,247116
add a comment |
up vote
1
down vote
accepted
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.
answered Nov 19 at 10:10
mathnoob
1,247116
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.
answered Nov 19 at 10:10
mathnoob
1,247116
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.
answered Nov 19 at 10:10
mathnoob
1,247116
answered Nov 19 at 10:10
mathnoob
1,247116
answered Nov 19 at 10:10
mathnoob
1,247116
answered Nov 19 at 10:10
mathnoob
1,247116
1,247116
add a comment |
add a comment |
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%2f3004728%2fshow-that-this-graph-is-k-connected%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
I'm not sure what first principles mean either but, presumably, it means to prove it from the definition of connectedness; Much like proving limits from first principles means to prove it from $epsilon$-$delta$. So you ought to prove by removing up to $k-1$ vertices the graph $G'$ remains connected.
– Sisyphus
Nov 19 at 10:11