If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$. I still cannot understand this statement. By definition of graph in my book, $G$ is a pair of $(V,E)$ where $V$ is vertices and $E$ is set of underordered pair of elements of $V$. If I set $V$ to be 3 vertices (1,2,3) and $E$ to be the edge connecting 1 and 2 but not the rest, then $G$ is not connected but there is only 1 connected component..? Sorry if it seems trivial cause my answer proof did not explain why.
graph-theory
asked Sep 8 at 5:48
ilovewt
911317
add a comment |Â
up vote
1
down vote
favorite
If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$. I still cannot understand this statement. By definition of graph in my book, $G$ is a pair of $(V,E)$ where $V$ is vertices and $E$ is set of underordered pair of elements of $V$. If I set $V$ to be 3 vertices (1,2,3) and $E$ to be the edge connecting 1 and 2 but not the rest, then $G$ is not connected but there is only 1 connected component..? Sorry if it seems trivial cause my answer proof did not explain why.
graph-theory
asked Sep 8 at 5:48
ilovewt
911317
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
2
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$. I still cannot understand this statement. By definition of graph in my book, $G$ is a pair of $(V,E)$ where $V$ is vertices and $E$ is set of underordered pair of elements of $V$. If I set $V$ to be 3 vertices (1,2,3) and $E$ to be the edge connecting 1 and 2 but not the rest, then $G$ is not connected but there is only 1 connected component..? Sorry if it seems trivial cause my answer proof did not explain why.
graph-theory
asked Sep 8 at 5:48
ilovewt
911317
If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$. I still cannot understand this statement. By definition of graph in my book, $G$ is a pair of $(V,E)$ where $V$ is vertices and $E$ is set of underordered pair of elements of $V$. If I set $V$ to be 3 vertices (1,2,3) and $E$ to be the edge connecting 1 and 2 but not the rest, then $G$ is not connected but there is only 1 connected component..? Sorry if it seems trivial cause my answer proof did not explain why.
graph-theory
graph-theory
asked Sep 8 at 5:48
ilovewt
911317
asked Sep 8 at 5:48
ilovewt
911317
asked Sep 8 at 5:48
ilovewt
911317
asked Sep 8 at 5:48
ilovewt
911317
asked Sep 8 at 5:48
ilovewt
911317
911317
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
2
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21
add a comment |Â
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
2
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
2
2
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.
Here's a fun exercise that you can prove: the relation $v sim w$ if there exists a path $xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.
answered Sep 8 at 5:52
Guido A.
4,806728
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.
Here's a fun exercise that you can prove: the relation $v sim w$ if there exists a path $xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.
answered Sep 8 at 5:52
Guido A.
4,806728
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
 |Â
show 2 more comments
up vote
1
down vote
accepted
By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.
Here's a fun exercise that you can prove: the relation $v sim w$ if there exists a path $xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.
answered Sep 8 at 5:52
Guido A.
4,806728
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
 |Â
show 2 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.
Here's a fun exercise that you can prove: the relation $v sim w$ if there exists a path $xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.
answered Sep 8 at 5:52
Guido A.
4,806728
By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.
Here's a fun exercise that you can prove: the relation $v sim w$ if there exists a path $xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.
answered Sep 8 at 5:52
Guido A.
4,806728
edited Sep 8 at 5:55
answered Sep 8 at 5:52
Guido A.
4,806728
answered Sep 8 at 5:52
Guido A.
4,806728
answered Sep 8 at 5:52
Guido A.
4,806728
4,806728
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
 |Â
show 2 more comments
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
I still do not understand why it implies $G$ is connected when $G$ has exactly one connected component?
– ilovewt
Sep 8 at 5:54
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Why do any two points belong to this subgraph?
– ilovewt
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
Take any two points. They must be in the same component. What does this mean? That they have a path from one to the other! This works for any two points, so they are all connected to each other by some path. This is the definition of connectedness.
– Guido A.
Sep 8 at 5:56
1
1
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
Exactly, that's it!
– Guido A.
Sep 8 at 5:58
1
1
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
Oh.. so I am missing out on the definition of connected components! Well, I really thought we can consider a disconnected graph but it has ONE connected graph inside, in which case, it makes me wonder why need at least 2 connected components haha.
– ilovewt
Sep 8 at 6:01
 |Â
show 2 more comments
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%2f2909315%2fif-g-is-a-graph-g-is-not-connected-then-there-are-at-least-2-connected-c%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
What are your definitions of connected graph and connected component?
– Guido A.
Sep 8 at 5:51
For connected graph it is any pair of vertices has a path connecting to it in the $G$ graph. For connected component I do not have it in my notes but after googling it should just mean a subgraph which is connected.
– ilovewt
Sep 8 at 5:52
Great, I was just checking that we were using the same defs.
– Guido A.
Sep 8 at 5:53
2
I take it you're not allowing the empty graph?
– Gerry Myerson
Sep 8 at 5:56
So is the graph consisting of a single vertex and no edges connected or not?
– Mark Bennet
Sep 8 at 6:21