Matching cardinality graphs
up vote
0
down vote
favorite
Show that a graph $G$ contains a matching of cardinality $p$ if and only if $q(G−S) le |S|+|G|−2p, ∀S ⊆ V (G)$.
//Again a problem that i encountered in my book about graphs theory.Any tip would be appreciated//
graph-theory
edited Nov 16 at 9:27
MathFun123
616318
asked Nov 16 at 8:15
John doe
132
add a comment |
up vote
0
down vote
favorite
Show that a graph $G$ contains a matching of cardinality $p$ if and only if $q(G−S) le |S|+|G|−2p, ∀S ⊆ V (G)$.
//Again a problem that i encountered in my book about graphs theory.Any tip would be appreciated//
graph-theory
edited Nov 16 at 9:27
MathFun123
616318
asked Nov 16 at 8:15
John doe
132
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Show that a graph $G$ contains a matching of cardinality $p$ if and only if $q(G−S) le |S|+|G|−2p, ∀S ⊆ V (G)$.
//Again a problem that i encountered in my book about graphs theory.Any tip would be appreciated//
graph-theory
edited Nov 16 at 9:27
MathFun123
616318
asked Nov 16 at 8:15
John doe
132
Show that a graph $G$ contains a matching of cardinality $p$ if and only if $q(G−S) le |S|+|G|−2p, ∀S ⊆ V (G)$.
//Again a problem that i encountered in my book about graphs theory.Any tip would be appreciated//
graph-theory
graph-theory
edited Nov 16 at 9:27
MathFun123
616318
asked Nov 16 at 8:15
John doe
132
edited Nov 16 at 9:27
MathFun123
616318
asked Nov 16 at 8:15
John doe
132
edited Nov 16 at 9:27
MathFun123
616318
edited Nov 16 at 9:27
MathFun123
616318
edited Nov 16 at 9:27
MathFun123
616318
616318
asked Nov 16 at 8:15
John doe
132
asked Nov 16 at 8:15
John doe
132
asked Nov 16 at 8:15
John doe
132
132
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11
add a comment |
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.
The Tutte-Berg formula is most useful in this situation.
Theorem (Tutte-Berg). Where $nu(G)$ denotes the size of a maximum matching of $G$,
begin{equation}
nu(G) = frac{1}{2} min_{U subseteq V(G)}( |U| - q(G - U) + |V(G)|).
end{equation}
For neccesity, it is clear that if we have a matching of size $p$, then $p leq nu(G)$. Moreover, for any $S subseteq V(G)$
begin{align}
p leq nu(G) &leq frac{1}{2}(|S| - q(G - S) + |G|)\
implies 2p &leq |S| - q(G - S) + |G|\
q(G - S) &leq |S| + |G| - 2p.
end{align}
We are done this direction since $S$ was arbitrary.
Conversely, it is enough to show that $p leq nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < nu(G)$ and for some $S subseteq V(G)$ satisfying $nu(G) = frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have
begin{align}
q(G - S) &leq |S| + |G| - 2p\
&< |S| + |G| - 2nu(G)\
&= |S| + |G| - (|S| - q(G - S) + |G|)\
&= q(G - S).
end{align}
That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p leq nu(G)$ as desired, allowing us to conclude.
answered Nov 26 at 6:57
S. O.
834
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',
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%2f3000874%2fmatching-cardinality-graphs%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
up vote
0
down vote
accepted
I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.
The Tutte-Berg formula is most useful in this situation.
Theorem (Tutte-Berg). Where $nu(G)$ denotes the size of a maximum matching of $G$,
begin{equation}
nu(G) = frac{1}{2} min_{U subseteq V(G)}( |U| - q(G - U) + |V(G)|).
end{equation}
For neccesity, it is clear that if we have a matching of size $p$, then $p leq nu(G)$. Moreover, for any $S subseteq V(G)$
begin{align}
p leq nu(G) &leq frac{1}{2}(|S| - q(G - S) + |G|)\
implies 2p &leq |S| - q(G - S) + |G|\
q(G - S) &leq |S| + |G| - 2p.
end{align}
We are done this direction since $S$ was arbitrary.
Conversely, it is enough to show that $p leq nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < nu(G)$ and for some $S subseteq V(G)$ satisfying $nu(G) = frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have
begin{align}
q(G - S) &leq |S| + |G| - 2p\
&< |S| + |G| - 2nu(G)\
&= |S| + |G| - (|S| - q(G - S) + |G|)\
&= q(G - S).
end{align}
That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p leq nu(G)$ as desired, allowing us to conclude.
answered Nov 26 at 6:57
S. O.
834
add a comment |
up vote
0
down vote
accepted
I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.
The Tutte-Berg formula is most useful in this situation.
Theorem (Tutte-Berg). Where $nu(G)$ denotes the size of a maximum matching of $G$,
begin{equation}
nu(G) = frac{1}{2} min_{U subseteq V(G)}( |U| - q(G - U) + |V(G)|).
end{equation}
For neccesity, it is clear that if we have a matching of size $p$, then $p leq nu(G)$. Moreover, for any $S subseteq V(G)$
begin{align}
p leq nu(G) &leq frac{1}{2}(|S| - q(G - S) + |G|)\
implies 2p &leq |S| - q(G - S) + |G|\
q(G - S) &leq |S| + |G| - 2p.
end{align}
We are done this direction since $S$ was arbitrary.
Conversely, it is enough to show that $p leq nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < nu(G)$ and for some $S subseteq V(G)$ satisfying $nu(G) = frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have
begin{align}
q(G - S) &leq |S| + |G| - 2p\
&< |S| + |G| - 2nu(G)\
&= |S| + |G| - (|S| - q(G - S) + |G|)\
&= q(G - S).
end{align}
That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p leq nu(G)$ as desired, allowing us to conclude.
answered Nov 26 at 6:57
S. O.
834
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.
The Tutte-Berg formula is most useful in this situation.
Theorem (Tutte-Berg). Where $nu(G)$ denotes the size of a maximum matching of $G$,
begin{equation}
nu(G) = frac{1}{2} min_{U subseteq V(G)}( |U| - q(G - U) + |V(G)|).
end{equation}
For neccesity, it is clear that if we have a matching of size $p$, then $p leq nu(G)$. Moreover, for any $S subseteq V(G)$
begin{align}
p leq nu(G) &leq frac{1}{2}(|S| - q(G - S) + |G|)\
implies 2p &leq |S| - q(G - S) + |G|\
q(G - S) &leq |S| + |G| - 2p.
end{align}
We are done this direction since $S$ was arbitrary.
Conversely, it is enough to show that $p leq nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < nu(G)$ and for some $S subseteq V(G)$ satisfying $nu(G) = frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have
begin{align}
q(G - S) &leq |S| + |G| - 2p\
&< |S| + |G| - 2nu(G)\
&= |S| + |G| - (|S| - q(G - S) + |G|)\
&= q(G - S).
end{align}
That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p leq nu(G)$ as desired, allowing us to conclude.
answered Nov 26 at 6:57
S. O.
834
I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.
The Tutte-Berg formula is most useful in this situation.
Theorem (Tutte-Berg). Where $nu(G)$ denotes the size of a maximum matching of $G$,
begin{equation}
nu(G) = frac{1}{2} min_{U subseteq V(G)}( |U| - q(G - U) + |V(G)|).
end{equation}
For neccesity, it is clear that if we have a matching of size $p$, then $p leq nu(G)$. Moreover, for any $S subseteq V(G)$
begin{align}
p leq nu(G) &leq frac{1}{2}(|S| - q(G - S) + |G|)\
implies 2p &leq |S| - q(G - S) + |G|\
q(G - S) &leq |S| + |G| - 2p.
end{align}
We are done this direction since $S$ was arbitrary.
Conversely, it is enough to show that $p leq nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < nu(G)$ and for some $S subseteq V(G)$ satisfying $nu(G) = frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have
begin{align}
q(G - S) &leq |S| + |G| - 2p\
&< |S| + |G| - 2nu(G)\
&= |S| + |G| - (|S| - q(G - S) + |G|)\
&= q(G - S).
end{align}
That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p leq nu(G)$ as desired, allowing us to conclude.
answered Nov 26 at 6:57
S. O.
834
answered Nov 26 at 6:57
S. O.
834
answered Nov 26 at 6:57
S. O.
834
answered Nov 26 at 6:57
S. O.
834
834
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.
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%2f3000874%2fmatching-cardinality-graphs%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
What is $q(G−S) $?
– hbm
Nov 16 at 14:02
I'm a little bit confused by your notation, but I'm thinking that this is some variant of Hall's condition. Hall's condition states that if the neighbors of every subset of G has a larger than the subset, then there is a perfect matching. So reapply that to $p$ instead of the entire graph.
– molocule
Nov 19 at 5:11