Infinite “connected” graphs and spanning trees
$begingroup$
Let us say that graph $G$ is quasi-connected iff for every two vertices there is either a finite path or an infinite path in sense of the offtopic of this answer.
Assuming the axiom of choice, is it true that every quasi-connected graph has a "spanning tree" (that is a subgraph where every pair of vertices is connected by unique finite or infinite path)?
graph-theory connectedness trees
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
$endgroup$
add a comment |
$begingroup$
Let us say that graph $G$ is quasi-connected iff for every two vertices there is either a finite path or an infinite path in sense of the offtopic of this answer.
Assuming the axiom of choice, is it true that every quasi-connected graph has a "spanning tree" (that is a subgraph where every pair of vertices is connected by unique finite or infinite path)?
graph-theory connectedness trees
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
$endgroup$
add a comment |
$begingroup$
Let us say that graph $G$ is quasi-connected iff for every two vertices there is either a finite path or an infinite path in sense of the offtopic of this answer.
Assuming the axiom of choice, is it true that every quasi-connected graph has a "spanning tree" (that is a subgraph where every pair of vertices is connected by unique finite or infinite path)?
graph-theory connectedness trees
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
$endgroup$
Let us say that graph $G$ is quasi-connected iff for every two vertices there is either a finite path or an infinite path in sense of the offtopic of this answer.
Assuming the axiom of choice, is it true that every quasi-connected graph has a "spanning tree" (that is a subgraph where every pair of vertices is connected by unique finite or infinite path)?
graph-theory connectedness trees
graph-theory connectedness trees
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
edited Dec 8 '18 at 23:54
Asaf Karagila♦
304k32431763
304k32431763
asked Dec 8 '18 at 23:00
byk7byk7
326110
asked Dec 8 '18 at 23:00
byk7byk7
326110
asked Dec 8 '18 at 23:00
byk7byk7
326110
326110
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes.
First choose an infinite ray in each of the (ordinarily) connected components, and extend it to a spanning tree.
Then, as long as there is still a subgraph isomorphic to $mathbb Z$ anywhere in the graph, select one of its edges and remove it. At some point (after possibly transfinitely many edge removals) you cannot remove more edges, and the graph is now a forest of trees with exactly one infinite branch each.
And a "tree" in the sense you define in your final parenthesis is exactly either an ordinary tree, or a forest of ordinary trees that each have exactly one infinite branch. To connect two nodes in different components you need to go from each of the nodes out the infinite branch of its component, and then connect those two rays at infinity.
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
$endgroup$
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
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%2f3031772%2finfinite-connected-graphs-and-spanning-trees%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
$begingroup$
Yes.
First choose an infinite ray in each of the (ordinarily) connected components, and extend it to a spanning tree.
Then, as long as there is still a subgraph isomorphic to $mathbb Z$ anywhere in the graph, select one of its edges and remove it. At some point (after possibly transfinitely many edge removals) you cannot remove more edges, and the graph is now a forest of trees with exactly one infinite branch each.
And a "tree" in the sense you define in your final parenthesis is exactly either an ordinary tree, or a forest of ordinary trees that each have exactly one infinite branch. To connect two nodes in different components you need to go from each of the nodes out the infinite branch of its component, and then connect those two rays at infinity.
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
$endgroup$
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
add a comment |
$begingroup$
Yes.
First choose an infinite ray in each of the (ordinarily) connected components, and extend it to a spanning tree.
Then, as long as there is still a subgraph isomorphic to $mathbb Z$ anywhere in the graph, select one of its edges and remove it. At some point (after possibly transfinitely many edge removals) you cannot remove more edges, and the graph is now a forest of trees with exactly one infinite branch each.
And a "tree" in the sense you define in your final parenthesis is exactly either an ordinary tree, or a forest of ordinary trees that each have exactly one infinite branch. To connect two nodes in different components you need to go from each of the nodes out the infinite branch of its component, and then connect those two rays at infinity.
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
$endgroup$
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
add a comment |
$begingroup$
Yes.
First choose an infinite ray in each of the (ordinarily) connected components, and extend it to a spanning tree.
Then, as long as there is still a subgraph isomorphic to $mathbb Z$ anywhere in the graph, select one of its edges and remove it. At some point (after possibly transfinitely many edge removals) you cannot remove more edges, and the graph is now a forest of trees with exactly one infinite branch each.
And a "tree" in the sense you define in your final parenthesis is exactly either an ordinary tree, or a forest of ordinary trees that each have exactly one infinite branch. To connect two nodes in different components you need to go from each of the nodes out the infinite branch of its component, and then connect those two rays at infinity.
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
$endgroup$
Yes.
First choose an infinite ray in each of the (ordinarily) connected components, and extend it to a spanning tree.
Then, as long as there is still a subgraph isomorphic to $mathbb Z$ anywhere in the graph, select one of its edges and remove it. At some point (after possibly transfinitely many edge removals) you cannot remove more edges, and the graph is now a forest of trees with exactly one infinite branch each.
And a "tree" in the sense you define in your final parenthesis is exactly either an ordinary tree, or a forest of ordinary trees that each have exactly one infinite branch. To connect two nodes in different components you need to go from each of the nodes out the infinite branch of its component, and then connect those two rays at infinity.
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
edited Dec 9 '18 at 0:25
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
answered Dec 9 '18 at 0:08
Henning MakholmHenning Makholm
240k17305542
240k17305542
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
add a comment |
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
$begingroup$
What do you mean by "a subgraph isomorphic to Z"? And "infinite branch" is "infinite path" or a ray in sense of the linked answer?
$endgroup$
– byk7
Dec 9 '18 at 0:53
1
1
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
@byk7: $mathbb Z$ is here shorthand for the graph that has a vertex for each integer and an edge between each integer and it successor. -- An "infinite path" is the same as a ray in the sense of the linked answer.
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:01
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
By a "tree with exactly one infinite branch" I mean a tree where you can choose a root node and there will be exactly one ray starting at that node. (This implies that if you choose a different node there will also be exactly one ray starting at that node).
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:04
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
Ok, thx. One more thing -- if you want to connect two rays, why they cannot be "separated forever" (like they are going in "opposite" directions or so)?
$endgroup$
– byk7
Dec 9 '18 at 1:20
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
$begingroup$
@byk7: No, by "connect two rays", I mean at the infinite ends, like what the linked answer described as "essentially the only new type of path that we gain from this generalisation". The generalisation has no concept of infinite rays going "in different directions" -- any two (disjoint) infinite rays may be joined in this way according to the proposed generalization of "path".
$endgroup$
– Henning Makholm
Dec 9 '18 at 1:46
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.
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%2f3031772%2finfinite-connected-graphs-and-spanning-trees%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
