Proof - A tree $T$ has a vertex of degree n and the others have degree $<n$. T has at least n leaves
$begingroup$
I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly logical reasoning. Any help?
discrete-mathematics graph-theory trees
edited Dec 24 '18 at 18:01
EdOverflow
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
$endgroup$
add a comment |
$begingroup$
I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly logical reasoning. Any help?
discrete-mathematics graph-theory trees
edited Dec 24 '18 at 18:01
EdOverflow
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
$endgroup$
1
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58
add a comment |
$begingroup$
I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly logical reasoning. Any help?
discrete-mathematics graph-theory trees
edited Dec 24 '18 at 18:01
EdOverflow
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
$endgroup$
I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly logical reasoning. Any help?
discrete-mathematics graph-theory trees
discrete-mathematics graph-theory trees
edited Dec 24 '18 at 18:01
EdOverflow
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
edited Dec 24 '18 at 18:01
EdOverflow
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
edited Dec 24 '18 at 18:01
EdOverflow
25119
edited Dec 24 '18 at 18:01
EdOverflow
25119
edited Dec 24 '18 at 18:01
EdOverflow
25119
25119
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
asked Dec 24 '18 at 17:44
PCNFPCNF
1338
1338
1
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58
add a comment |
1
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58
1
1
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.
Notice $sumlimits_{i=1}^v (v_i-1) = v-2$
Without loss of generality $v_1=n$
This means $sumlimits_{i=2}^v (v_i-1) = v-n-1$
So at least $n$ of the summands are equal to $0$.
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
add a comment |
$begingroup$
Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $ineq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.
Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$implies $we get $k$ leaves from them $implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $implies T$ has at least $(n-k)+k=n$ leaves!
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
$endgroup$
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
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%2f3051493%2fproof-a-tree-t-has-a-vertex-of-degree-n-and-the-others-have-degree-n-t-h%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.
Notice $sumlimits_{i=1}^v (v_i-1) = v-2$
Without loss of generality $v_1=n$
This means $sumlimits_{i=2}^v (v_i-1) = v-n-1$
So at least $n$ of the summands are equal to $0$.
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
add a comment |
$begingroup$
Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.
Notice $sumlimits_{i=1}^v (v_i-1) = v-2$
Without loss of generality $v_1=n$
This means $sumlimits_{i=2}^v (v_i-1) = v-n-1$
So at least $n$ of the summands are equal to $0$.
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
add a comment |
$begingroup$
Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.
Notice $sumlimits_{i=1}^v (v_i-1) = v-2$
Without loss of generality $v_1=n$
This means $sumlimits_{i=2}^v (v_i-1) = v-n-1$
So at least $n$ of the summands are equal to $0$.
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.
Notice $sumlimits_{i=1}^v (v_i-1) = v-2$
Without loss of generality $v_1=n$
This means $sumlimits_{i=2}^v (v_i-1) = v-n-1$
So at least $n$ of the summands are equal to $0$.
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
answered Dec 24 '18 at 18:24
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
76.8k1294195
add a comment |
add a comment |
$begingroup$
Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $ineq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.
Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$implies $we get $k$ leaves from them $implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $implies T$ has at least $(n-k)+k=n$ leaves!
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
$endgroup$
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
add a comment |
$begingroup$
Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $ineq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.
Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$implies $we get $k$ leaves from them $implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $implies T$ has at least $(n-k)+k=n$ leaves!
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
$endgroup$
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
add a comment |
$begingroup$
Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $ineq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.
Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$implies $we get $k$ leaves from them $implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $implies T$ has at least $(n-k)+k=n$ leaves!
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
$endgroup$
Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $ineq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.
Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$implies $we get $k$ leaves from them $implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $implies T$ has at least $(n-k)+k=n$ leaves!
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
edited Dec 24 '18 at 19:03
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
answered Dec 24 '18 at 17:57
Ankit KumarAnkit Kumar
1,516221
1,516221
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
add a comment |
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
Thanks, but I didn't understand the last part. It's clear that you can divide $T$ into $T_n$ components which are trees. It is not clear to me how you go from these considerations to saying that T has n leaves.
$endgroup$
– PCNF
Dec 24 '18 at 18:20
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
$begingroup$
(1) Do you agree deleting u won't affect the number of leaves? (2) Do you agree that every tree has at least one leaf? (3) Do you agree that deleting u will lead to n (sub-)trees? If it's all yes, you're done ;)
$endgroup$
– Ankit Kumar
Dec 24 '18 at 18:21
1
1
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
$begingroup$
Apparently, everything is clear but I can not apply what I said to a simple example. For example, I have the tree 1-2-3 and the vertex 2 is connected to a vertex 4. So, if I delete the vertex 2 which has the maximum degree, I obtain the vertex 1,3,4 without the vertex 2 that they shared. How do I continue now?
$endgroup$
– PCNF
Dec 24 '18 at 18:42
2
2
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
I think if you want your proof to be complete, you should replace the phrase "every tree has at least a leaf" with "every tree has at least two leaves." A leaf in $T_i$ might not be a leaf in $T$, if that leaf was originally joined to $u$.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:52
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
$begingroup$
Fixed everything now. Thank you for comments @MikeEarnest and PCNF
$endgroup$
– Ankit Kumar
Dec 24 '18 at 19:04
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%2f3051493%2fproof-a-tree-t-has-a-vertex-of-degree-n-and-the-others-have-degree-n-t-h%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
1
$begingroup$
Hint: if you delete the vertex of degree $n$, then $n$ disjoint trees remain. How many leaves do each of those trees have?
$endgroup$
– Mike Earnest
Dec 24 '18 at 17:53
$begingroup$
@MikeEarnest sorry... i saw your comment after I posted my answer
$endgroup$
– Ankit Kumar
Dec 24 '18 at 17:58