Mixing
Adding one edge to a tree creates exactly one cycle
2
$begingroup$
I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?
trees
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
$endgroup$
add a comment |
2
$begingroup$
I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?
trees
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
$endgroup$
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14
add a comment |
2
2
2
$begingroup$
I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?
trees
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
$endgroup$
I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?
trees
trees
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
asked Feb 19 '16 at 23:00
greatSharkgreatShark
111
111
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14
add a comment |
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14
add a comment |
1 Answer
1
active
oldest
votes
0
$begingroup$
This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
$endgroup$
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
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
});
}
});
draft saved
draft discarded
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%2f1663565%2fadding-one-edge-to-a-tree-creates-exactly-one-cycle%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
0
$begingroup$
This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
$endgroup$
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
add a comment |
0
$begingroup$
This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
$endgroup$
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
add a comment |
0
0
0
$begingroup$
This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
$endgroup$
This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
edited Feb 19 '16 at 23:10
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
answered Feb 19 '16 at 23:06
Igor RivinIgor Rivin
16k11234
16k11234
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
add a comment |
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
I think the question assumes the same vertex set
$endgroup$
– Shailesh
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:08
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
$begingroup$
@JMoravitz Different people mean different things by "add an edge".
$endgroup$
– Igor Rivin
Feb 19 '16 at 23:11
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f1663565%2fadding-one-edge-to-a-tree-creates-exactly-one-cycle%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
$begingroup$
What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above.
$endgroup$
– JMoravitz
Feb 19 '16 at 23:06
$begingroup$
Try reading the following: math.stackexchange.com/questions/325279/…, math.stackexchange.com/questions/1118176/…, math.stackexchange.com/questions/1569073/…
$endgroup$
– JMoravitz
Feb 19 '16 at 23:10
$begingroup$
Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle.
$endgroup$
– Brian M. Scott
Feb 19 '16 at 23:14