The minimum edge cover of a tree is at least the maximum degree
$begingroup$
Let $T$ be a tree with maximum degree $Delta(T)$, and let $beta'(T)$ denote the size of the minimum edge cover of $T$. The question is to prove that $beta'(T) ge Delta(T)$.
I started by proving that each tree has at least $Delta(T)$ using induction on $n$. Then I tried using the fact that if we take the edge connected to each leaf then we will have minimum edge coverage equal to $Delta(T)$ in case all the leaves are connected to the vertex of max degree, if not, then we need at least one more edge. Does it make sense?
graph-theory
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
$endgroup$
add a comment |
$begingroup$
Let $T$ be a tree with maximum degree $Delta(T)$, and let $beta'(T)$ denote the size of the minimum edge cover of $T$. The question is to prove that $beta'(T) ge Delta(T)$.
I started by proving that each tree has at least $Delta(T)$ using induction on $n$. Then I tried using the fact that if we take the edge connected to each leaf then we will have minimum edge coverage equal to $Delta(T)$ in case all the leaves are connected to the vertex of max degree, if not, then we need at least one more edge. Does it make sense?
graph-theory
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
$endgroup$
1
$begingroup$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07
add a comment |
$begingroup$
Let $T$ be a tree with maximum degree $Delta(T)$, and let $beta'(T)$ denote the size of the minimum edge cover of $T$. The question is to prove that $beta'(T) ge Delta(T)$.
I started by proving that each tree has at least $Delta(T)$ using induction on $n$. Then I tried using the fact that if we take the edge connected to each leaf then we will have minimum edge coverage equal to $Delta(T)$ in case all the leaves are connected to the vertex of max degree, if not, then we need at least one more edge. Does it make sense?
graph-theory
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
$endgroup$
Let $T$ be a tree with maximum degree $Delta(T)$, and let $beta'(T)$ denote the size of the minimum edge cover of $T$. The question is to prove that $beta'(T) ge Delta(T)$.
I started by proving that each tree has at least $Delta(T)$ using induction on $n$. Then I tried using the fact that if we take the edge connected to each leaf then we will have minimum edge coverage equal to $Delta(T)$ in case all the leaves are connected to the vertex of max degree, if not, then we need at least one more edge. Does it make sense?
graph-theory
graph-theory
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
edited Dec 9 '18 at 16:38
Misha Lavrov
46.4k657107
46.4k657107
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
asked Dec 9 '18 at 16:01
Mera InsanMera Insan
176
176
1
$begingroup$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07
add a comment |
1
$begingroup$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07
1
1
$begingroup$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $beta'(T) = Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.
In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like
and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.
There are two strategies that you could pursue:
- The tree $T$ has $Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $Delta(T)$ edges.
- You could prove that $T$ has at least $Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $Delta(T)$ edges that must be in the edge cover no matter what.
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
$endgroup$
add a comment |
$begingroup$
Let $v$ be a vertex of a maximal degree $Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=Delta$ distinct vertices to cover $N(v)$.
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
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%2f3032549%2fthe-minimum-edge-cover-of-a-tree-is-at-least-the-maximum-degree%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$
In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $beta'(T) = Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.
In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like
and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.
There are two strategies that you could pursue:
- The tree $T$ has $Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $Delta(T)$ edges.
- You could prove that $T$ has at least $Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $Delta(T)$ edges that must be in the edge cover no matter what.
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
$endgroup$
add a comment |
$begingroup$
In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $beta'(T) = Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.
In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like
and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.
There are two strategies that you could pursue:
- The tree $T$ has $Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $Delta(T)$ edges.
- You could prove that $T$ has at least $Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $Delta(T)$ edges that must be in the edge cover no matter what.
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
$endgroup$
add a comment |
$begingroup$
In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $beta'(T) = Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.
In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like
and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.
There are two strategies that you could pursue:
- The tree $T$ has $Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $Delta(T)$ edges.
- You could prove that $T$ has at least $Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $Delta(T)$ edges that must be in the edge cover no matter what.
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
$endgroup$
In the case where there is only one vertex of maximum degree in $T$, and it's adjacent to all other vertices, you are right that $beta'(T) = Delta(T)$, and we can prove this by looking at the edges that cover each of the other vertices.
In other cases, you claim that we need at least one more edge. First of all, this is not always true: we could have a tree that looks like
and this is still possible to cover with $5$ edges. Whether true or false, it needs more proof. You are probably thinking something like "if we take the edge cover we were using previously, which consisted of all the edges incident to the maximum-degree vertex, then that doesn't work anymore and it needs one more edge". But that doesn't mean there's not some more clever strategy, which doesn't start with that edge cover to begin with.
There are two strategies that you could pursue:
- The tree $T$ has $Delta(T)$ branches stemming off of a vertex of maximum degree. You could argue that each of these branches needs at least one edge to cover it, and that no edge can cover two branches. It follows that any edge cover needs at least $Delta(T)$ edges.
- You could prove that $T$ has at least $Delta(T)$ leaves. Each leaf can only be covered by one edge, and these are all distinct, so this gives $Delta(T)$ edges that must be in the edge cover no matter what.
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
answered Dec 9 '18 at 16:37
Misha LavrovMisha Lavrov
46.4k657107
46.4k657107
add a comment |
add a comment |
$begingroup$
Let $v$ be a vertex of a maximal degree $Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=Delta$ distinct vertices to cover $N(v)$.
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
add a comment |
$begingroup$
Let $v$ be a vertex of a maximal degree $Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=Delta$ distinct vertices to cover $N(v)$.
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
add a comment |
$begingroup$
Let $v$ be a vertex of a maximal degree $Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=Delta$ distinct vertices to cover $N(v)$.
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
Let $v$ be a vertex of a maximal degree $Delta$ of the tree $T$. Let $N(v)$ be a set of neighbors of the vertex $v$. If any edge of $T$ is incident to at least two vertices $v,w$ of $N(v)$ then $u-v-w-u$ is a cycle, which cannot occur in a tree. So each edge cover need at least $|N(v)|=Delta$ distinct vertices to cover $N(v)$.
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
answered Dec 9 '18 at 16:34
Alex RavskyAlex Ravsky
41.5k32282
41.5k32282
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.
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%2f3032549%2fthe-minimum-edge-cover-of-a-tree-is-at-least-the-maximum-degree%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$
By B'(T) do you mean $beta'(T)$, and is this the minimum size of an edge cover of $T$? By △T do you mean $Delta(T)$, and is this the maximum degree of $T$? Are you assuming that $T$ is a tree? Especially in graph theory where a lot of notation is relatively new, you should define your terms before you use them. But in general, you shouldn't ask questions that require everyone to read your mind.
$endgroup$
– Misha Lavrov
Dec 9 '18 at 16:06
$begingroup$
Yes, B'(T) is the minimum size of edge coverage, $triangle$ T is maximum degree of T. T is a tree
$endgroup$
– Mera Insan
Dec 9 '18 at 16:07