Let M be a matching of T, prove that M< N(T) - $triangle$ (T).
This question is part C of another question:
(a) Using induction on $n$, prove that $T$ has at least $Delta(T)$ leaves.
(b) Prove that $B'(T) geq Delta (T)$.
(c) Let $M$ be a matching of $T$, prove that $M leq N(T) - Delta (T)$.
Where $Delta(T)$ = Max degree in $T$ and
$B'(T)$ = Size of a minimum edge cover
N(T)= number of vertices in T
Attempt
I have already proved parts a and b, and just need a bit of improvement on part c. Since $T$ is an acyclic graph, then it is bipartite.
Also, since $ B'(T) + alpha '(T) = N(T)$,
where $alpha'(T) $ = size of a maximum matching in T, from b we can say that $alpha'(T) leq N(T) - Delta (T)$.
The problem is I am not sure if the question is talking about maximum matching or any matching in $T$. How can I improve my proof to accommodate any matching in $T$?
proof-verification graph-theory
asked Dec 10 '18 at 5:07
Mera Insan
176
|
show 2 more comments
This question is part C of another question:
(a) Using induction on $n$, prove that $T$ has at least $Delta(T)$ leaves.
(b) Prove that $B'(T) geq Delta (T)$.
(c) Let $M$ be a matching of $T$, prove that $M leq N(T) - Delta (T)$.
Where $Delta(T)$ = Max degree in $T$ and
$B'(T)$ = Size of a minimum edge cover
N(T)= number of vertices in T
Attempt
I have already proved parts a and b, and just need a bit of improvement on part c. Since $T$ is an acyclic graph, then it is bipartite.
Also, since $ B'(T) + alpha '(T) = N(T)$,
where $alpha'(T) $ = size of a maximum matching in T, from b we can say that $alpha'(T) leq N(T) - Delta (T)$.
The problem is I am not sure if the question is talking about maximum matching or any matching in $T$. How can I improve my proof to accommodate any matching in $T$?
proof-verification graph-theory
asked Dec 10 '18 at 5:07
Mera Insan
176
1
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20
|
show 2 more comments
This question is part C of another question:
(a) Using induction on $n$, prove that $T$ has at least $Delta(T)$ leaves.
(b) Prove that $B'(T) geq Delta (T)$.
(c) Let $M$ be a matching of $T$, prove that $M leq N(T) - Delta (T)$.
Where $Delta(T)$ = Max degree in $T$ and
$B'(T)$ = Size of a minimum edge cover
N(T)= number of vertices in T
Attempt
I have already proved parts a and b, and just need a bit of improvement on part c. Since $T$ is an acyclic graph, then it is bipartite.
Also, since $ B'(T) + alpha '(T) = N(T)$,
where $alpha'(T) $ = size of a maximum matching in T, from b we can say that $alpha'(T) leq N(T) - Delta (T)$.
The problem is I am not sure if the question is talking about maximum matching or any matching in $T$. How can I improve my proof to accommodate any matching in $T$?
proof-verification graph-theory
asked Dec 10 '18 at 5:07
Mera Insan
176
This question is part C of another question:
(a) Using induction on $n$, prove that $T$ has at least $Delta(T)$ leaves.
(b) Prove that $B'(T) geq Delta (T)$.
(c) Let $M$ be a matching of $T$, prove that $M leq N(T) - Delta (T)$.
Where $Delta(T)$ = Max degree in $T$ and
$B'(T)$ = Size of a minimum edge cover
N(T)= number of vertices in T
Attempt
I have already proved parts a and b, and just need a bit of improvement on part c. Since $T$ is an acyclic graph, then it is bipartite.
Also, since $ B'(T) + alpha '(T) = N(T)$,
where $alpha'(T) $ = size of a maximum matching in T, from b we can say that $alpha'(T) leq N(T) - Delta (T)$.
The problem is I am not sure if the question is talking about maximum matching or any matching in $T$. How can I improve my proof to accommodate any matching in $T$?
proof-verification graph-theory
proof-verification graph-theory
asked Dec 10 '18 at 5:07
Mera Insan
176
asked Dec 10 '18 at 5:07
Mera Insan
176
edited Dec 10 '18 at 5:22
asked Dec 10 '18 at 5:07
Mera Insan
176
asked Dec 10 '18 at 5:07
Mera Insan
176
asked Dec 10 '18 at 5:07
Mera Insan
176
176
1
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20
|
show 2 more comments
1
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20
1
1
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20
|
show 2 more comments
1 Answer
1
active
oldest
votes
Your proof seems to be missing the justification for $B'(T) + alpha'(T) = N(T)$. If you have already shown this separately, then this proof would work for an arbitrary matching $M$, since for any such matching, $|M| leq alpha'(T)$.
answered Dec 10 '18 at 5:28
platty
3,370320
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
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%2f3033475%2flet-m-be-a-matching-of-t-prove-that-m-nt-triangle-t%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
Your proof seems to be missing the justification for $B'(T) + alpha'(T) = N(T)$. If you have already shown this separately, then this proof would work for an arbitrary matching $M$, since for any such matching, $|M| leq alpha'(T)$.
answered Dec 10 '18 at 5:28
platty
3,370320
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
add a comment |
Your proof seems to be missing the justification for $B'(T) + alpha'(T) = N(T)$. If you have already shown this separately, then this proof would work for an arbitrary matching $M$, since for any such matching, $|M| leq alpha'(T)$.
answered Dec 10 '18 at 5:28
platty
3,370320
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
add a comment |
Your proof seems to be missing the justification for $B'(T) + alpha'(T) = N(T)$. If you have already shown this separately, then this proof would work for an arbitrary matching $M$, since for any such matching, $|M| leq alpha'(T)$.
answered Dec 10 '18 at 5:28
platty
3,370320
Your proof seems to be missing the justification for $B'(T) + alpha'(T) = N(T)$. If you have already shown this separately, then this proof would work for an arbitrary matching $M$, since for any such matching, $|M| leq alpha'(T)$.
answered Dec 10 '18 at 5:28
platty
3,370320
answered Dec 10 '18 at 5:28
platty
3,370320
answered Dec 10 '18 at 5:28
platty
3,370320
answered Dec 10 '18 at 5:28
platty
3,370320
3,370320
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
add a comment |
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
Yes, I proved that. Thanks for your help
– Mera Insan
Dec 10 '18 at 5:31
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%2f3033475%2flet-m-be-a-matching-of-t-prove-that-m-nt-triangle-t%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
If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| leq |M|$ by definition.
– platty
Dec 10 '18 at 5:12
Okay, I will add it. Is my proof complete then?
– Mera Insan
Dec 10 '18 at 5:12
Do you mean to say that $alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover?
– platty
Dec 10 '18 at 5:15
Yes, this is what I meant
– Mera Insan
Dec 10 '18 at 5:16
You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices?
– platty
Dec 10 '18 at 5:20