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 19 hours ago
user499701
947
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 19 hours ago
user499701
947
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
19 hours ago
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 19 hours ago
user499701
947
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 19 hours ago
user499701
947
asked 19 hours ago
user499701
947
asked 19 hours ago
user499701
947
asked 19 hours ago
user499701
947
asked 19 hours ago
user499701
947
947
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
19 hours ago
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
19 hours ago
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
19 hours ago
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
19 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
$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 19 hours ago
mathnoob
54011
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
$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 19 hours ago
mathnoob
54011
add a comment |
up vote
0
down vote
$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 19 hours ago
mathnoob
54011
add a comment |
up vote
0
down vote
up vote
0
down vote
$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 19 hours ago
mathnoob
54011
$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 19 hours ago
mathnoob
54011
answered 19 hours ago
mathnoob
54011
answered 19 hours ago
mathnoob
54011
answered 19 hours ago
mathnoob
54011
54011
add a comment |
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
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
19 hours ago