A path-connected graph is connected as a graph
This question regards the difference between being path-connected as a topological space, i.e. "Every two point $x,y in X$ can be connected with a path" and being connected in a graph sense: "A graph $G$ is connected if there is a path in $G$ between any pair of distinct vertices."
I can see that being connected in a graph sense implies being path connected in a topological sense, but how do I show that being path connected in a topological sense implies being connected as a graph (at least for finite graphs)?
general-topology graph-theory connectedness path-connected
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
add a comment |
This question regards the difference between being path-connected as a topological space, i.e. "Every two point $x,y in X$ can be connected with a path" and being connected in a graph sense: "A graph $G$ is connected if there is a path in $G$ between any pair of distinct vertices."
I can see that being connected in a graph sense implies being path connected in a topological sense, but how do I show that being path connected in a topological sense implies being connected as a graph (at least for finite graphs)?
general-topology graph-theory connectedness path-connected
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
2
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20
add a comment |
This question regards the difference between being path-connected as a topological space, i.e. "Every two point $x,y in X$ can be connected with a path" and being connected in a graph sense: "A graph $G$ is connected if there is a path in $G$ between any pair of distinct vertices."
I can see that being connected in a graph sense implies being path connected in a topological sense, but how do I show that being path connected in a topological sense implies being connected as a graph (at least for finite graphs)?
general-topology graph-theory connectedness path-connected
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
This question regards the difference between being path-connected as a topological space, i.e. "Every two point $x,y in X$ can be connected with a path" and being connected in a graph sense: "A graph $G$ is connected if there is a path in $G$ between any pair of distinct vertices."
I can see that being connected in a graph sense implies being path connected in a topological sense, but how do I show that being path connected in a topological sense implies being connected as a graph (at least for finite graphs)?
general-topology graph-theory connectedness path-connected
general-topology graph-theory connectedness path-connected
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
asked Jan 4 at 14:04
Rasmus Søgaard ChristensenRasmus Søgaard Christensen
617
617
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
2
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20
add a comment |
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
2
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
2
2
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20
add a comment |
1 Answer
1
active
oldest
votes
Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $T(G)$ be its topological realization. I will use the following fact
Lemma. If $G$ is a disjoint union of two subgraphs then $T(G)$ is a (topological) disjoint union of two spaces, each one being a topological realization of appropriate subgraphs of $G$. Furthermore if $v,win V$ lie in different (graph) components then $v,w$ lie in different connected components of $T(G)$.
Proof. Assume that that $G=G_1sqcup G_2$ as graphs, i.e. $G=G_1cup G_2$ and there is no path between $G_1$ and $G_2$. Consider $T(G_1)$ and $T(G_2)$ which are subsets of $T(G)$. It can be easily seen that $T(G_1)cap T(G_2)=emptyset$. Otherwise there would be either an edge between $G_1$ and $G_2$ or they would share a vertex. Since both $T(G_1)$ and $T(G_2)$ are closed (as full subgraphs always are) then $T(G)=T(G_1)sqcup T(G_2)$. $Box$
As you've noted it is trivial to see that every graph path induces topological path because edges correspond to subspaces of $T(G)$ homeomorphic to $[0,1]$.
Now assume that $lambda:[0,1]to T(G)$ is a path between two vertices $v,w$. Assume that there is no graph path from $v$ to $w$. It follows that $G$ is a disjoint union of two subgraphs: one containing $v$ (the graph path component of $v$) and the other containing $w$ (the complement). By the lemma this implies that $T(G)$ is a disjoint union of appropriate topological realizations. In particular $v,w$ lie in different connected components and thus cannot be connected by a path. Contradiction.
answered yesterday
freakishfreakish
11.7k1629
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3061674%2fa-path-connected-graph-is-connected-as-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $T(G)$ be its topological realization. I will use the following fact
Lemma. If $G$ is a disjoint union of two subgraphs then $T(G)$ is a (topological) disjoint union of two spaces, each one being a topological realization of appropriate subgraphs of $G$. Furthermore if $v,win V$ lie in different (graph) components then $v,w$ lie in different connected components of $T(G)$.
Proof. Assume that that $G=G_1sqcup G_2$ as graphs, i.e. $G=G_1cup G_2$ and there is no path between $G_1$ and $G_2$. Consider $T(G_1)$ and $T(G_2)$ which are subsets of $T(G)$. It can be easily seen that $T(G_1)cap T(G_2)=emptyset$. Otherwise there would be either an edge between $G_1$ and $G_2$ or they would share a vertex. Since both $T(G_1)$ and $T(G_2)$ are closed (as full subgraphs always are) then $T(G)=T(G_1)sqcup T(G_2)$. $Box$
As you've noted it is trivial to see that every graph path induces topological path because edges correspond to subspaces of $T(G)$ homeomorphic to $[0,1]$.
Now assume that $lambda:[0,1]to T(G)$ is a path between two vertices $v,w$. Assume that there is no graph path from $v$ to $w$. It follows that $G$ is a disjoint union of two subgraphs: one containing $v$ (the graph path component of $v$) and the other containing $w$ (the complement). By the lemma this implies that $T(G)$ is a disjoint union of appropriate topological realizations. In particular $v,w$ lie in different connected components and thus cannot be connected by a path. Contradiction.
answered yesterday
freakishfreakish
11.7k1629
add a comment |
Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $T(G)$ be its topological realization. I will use the following fact
Lemma. If $G$ is a disjoint union of two subgraphs then $T(G)$ is a (topological) disjoint union of two spaces, each one being a topological realization of appropriate subgraphs of $G$. Furthermore if $v,win V$ lie in different (graph) components then $v,w$ lie in different connected components of $T(G)$.
Proof. Assume that that $G=G_1sqcup G_2$ as graphs, i.e. $G=G_1cup G_2$ and there is no path between $G_1$ and $G_2$. Consider $T(G_1)$ and $T(G_2)$ which are subsets of $T(G)$. It can be easily seen that $T(G_1)cap T(G_2)=emptyset$. Otherwise there would be either an edge between $G_1$ and $G_2$ or they would share a vertex. Since both $T(G_1)$ and $T(G_2)$ are closed (as full subgraphs always are) then $T(G)=T(G_1)sqcup T(G_2)$. $Box$
As you've noted it is trivial to see that every graph path induces topological path because edges correspond to subspaces of $T(G)$ homeomorphic to $[0,1]$.
Now assume that $lambda:[0,1]to T(G)$ is a path between two vertices $v,w$. Assume that there is no graph path from $v$ to $w$. It follows that $G$ is a disjoint union of two subgraphs: one containing $v$ (the graph path component of $v$) and the other containing $w$ (the complement). By the lemma this implies that $T(G)$ is a disjoint union of appropriate topological realizations. In particular $v,w$ lie in different connected components and thus cannot be connected by a path. Contradiction.
answered yesterday
freakishfreakish
11.7k1629
add a comment |
Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $T(G)$ be its topological realization. I will use the following fact
Lemma. If $G$ is a disjoint union of two subgraphs then $T(G)$ is a (topological) disjoint union of two spaces, each one being a topological realization of appropriate subgraphs of $G$. Furthermore if $v,win V$ lie in different (graph) components then $v,w$ lie in different connected components of $T(G)$.
Proof. Assume that that $G=G_1sqcup G_2$ as graphs, i.e. $G=G_1cup G_2$ and there is no path between $G_1$ and $G_2$. Consider $T(G_1)$ and $T(G_2)$ which are subsets of $T(G)$. It can be easily seen that $T(G_1)cap T(G_2)=emptyset$. Otherwise there would be either an edge between $G_1$ and $G_2$ or they would share a vertex. Since both $T(G_1)$ and $T(G_2)$ are closed (as full subgraphs always are) then $T(G)=T(G_1)sqcup T(G_2)$. $Box$
As you've noted it is trivial to see that every graph path induces topological path because edges correspond to subspaces of $T(G)$ homeomorphic to $[0,1]$.
Now assume that $lambda:[0,1]to T(G)$ is a path between two vertices $v,w$. Assume that there is no graph path from $v$ to $w$. It follows that $G$ is a disjoint union of two subgraphs: one containing $v$ (the graph path component of $v$) and the other containing $w$ (the complement). By the lemma this implies that $T(G)$ is a disjoint union of appropriate topological realizations. In particular $v,w$ lie in different connected components and thus cannot be connected by a path. Contradiction.
answered yesterday
freakishfreakish
11.7k1629
Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $T(G)$ be its topological realization. I will use the following fact
Lemma. If $G$ is a disjoint union of two subgraphs then $T(G)$ is a (topological) disjoint union of two spaces, each one being a topological realization of appropriate subgraphs of $G$. Furthermore if $v,win V$ lie in different (graph) components then $v,w$ lie in different connected components of $T(G)$.
Proof. Assume that that $G=G_1sqcup G_2$ as graphs, i.e. $G=G_1cup G_2$ and there is no path between $G_1$ and $G_2$. Consider $T(G_1)$ and $T(G_2)$ which are subsets of $T(G)$. It can be easily seen that $T(G_1)cap T(G_2)=emptyset$. Otherwise there would be either an edge between $G_1$ and $G_2$ or they would share a vertex. Since both $T(G_1)$ and $T(G_2)$ are closed (as full subgraphs always are) then $T(G)=T(G_1)sqcup T(G_2)$. $Box$
As you've noted it is trivial to see that every graph path induces topological path because edges correspond to subspaces of $T(G)$ homeomorphic to $[0,1]$.
Now assume that $lambda:[0,1]to T(G)$ is a path between two vertices $v,w$. Assume that there is no graph path from $v$ to $w$. It follows that $G$ is a disjoint union of two subgraphs: one containing $v$ (the graph path component of $v$) and the other containing $w$ (the complement). By the lemma this implies that $T(G)$ is a disjoint union of appropriate topological realizations. In particular $v,w$ lie in different connected components and thus cannot be connected by a path. Contradiction.
answered yesterday
freakishfreakish
11.7k1629
edited yesterday
answered yesterday
freakishfreakish
11.7k1629
answered yesterday
freakishfreakish
11.7k1629
answered yesterday
freakishfreakish
11.7k1629
11.7k1629
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%2f3061674%2fa-path-connected-graph-is-connected-as-a-graph%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
Both say that there is a path between any two vertices, I don’t see what the problem is.
– Zachary Hunter
Jan 4 at 15:22
2
@ZacharyHunter The problem is that the word "path" means different thing in each context. In graph theory it is a sequence of vertices $(v_1,ldots, v_n)$ such that there is an edge between $(v_i, v_{i+1})$. In topology it is a continuous function $f:[0,1]to G$. Note that here by $G$ we understand the topological realization of $G$.
– freakish
Jan 4 at 16:18
And as OP noted every graph path induces topological path. This is quite obvious, because every edge between $(v,w)$ induces a topological path. This is an immediate consequence of the construction of the topological realization. But the other way around seems harder. In other words: how to extract a sequence of vertices and edges from a given path $[0,1]to G$? Note subtleties: for example a topological path can pass infinitely many times through vertices (even in a finite graph). This cannot happen for a graph path.
– freakish
Jan 4 at 16:20