Mixing
Constructing a pair of matchings with needed characteristics
$begingroup$
I'm studying for a test in Graph Theory and I don't know how to prove that Union and intersection part of the following exercise:
Let $M$ and $N$ be matchings in a graph $G$ with $|M|>|N|$. Then there exist matchings $M'$ and $N'$ in $G$ such that $|M'|=|M|-1, |N'|=|N|+1, M' cap N' = M cap N$ and $M' cup N'=M cup N$.
What I have until now:
I know that as $|M| > |N|$ then $N$ is not a maximum matching, so there is an $N$-augmenting path and therefore there is an $N'$ such that $|N'| = |N|+1$.
I think I can see $N= M'$ and $M=N'$ but I don't know how to prove it formally.
Let call $T$ to $G[MDelta N]=Mcup N−Mcup N$ Which each vertex in $T$ has a degree either one or two. Also, any component of $T$ is either an even cycle or a path with edges alternately in $M$ and $N$, where at least one path have starting and ending in $M$ because of the condition $|M|> |N|$.
P.D. Some modifications of the question have been done according to the hints given by @LeenDroogendijk
graph-theory
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
$endgroup$
add a comment |
$begingroup$
I'm studying for a test in Graph Theory and I don't know how to prove that Union and intersection part of the following exercise:
Let $M$ and $N$ be matchings in a graph $G$ with $|M|>|N|$. Then there exist matchings $M'$ and $N'$ in $G$ such that $|M'|=|M|-1, |N'|=|N|+1, M' cap N' = M cap N$ and $M' cup N'=M cup N$.
What I have until now:
I know that as $|M| > |N|$ then $N$ is not a maximum matching, so there is an $N$-augmenting path and therefore there is an $N'$ such that $|N'| = |N|+1$.
I think I can see $N= M'$ and $M=N'$ but I don't know how to prove it formally.
Let call $T$ to $G[MDelta N]=Mcup N−Mcup N$ Which each vertex in $T$ has a degree either one or two. Also, any component of $T$ is either an even cycle or a path with edges alternately in $M$ and $N$, where at least one path have starting and ending in $M$ because of the condition $|M|> |N|$.
P.D. Some modifications of the question have been done according to the hints given by @LeenDroogendijk
graph-theory
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
$endgroup$
1
$begingroup$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32
add a comment |
$begingroup$
I'm studying for a test in Graph Theory and I don't know how to prove that Union and intersection part of the following exercise:
Let $M$ and $N$ be matchings in a graph $G$ with $|M|>|N|$. Then there exist matchings $M'$ and $N'$ in $G$ such that $|M'|=|M|-1, |N'|=|N|+1, M' cap N' = M cap N$ and $M' cup N'=M cup N$.
What I have until now:
I know that as $|M| > |N|$ then $N$ is not a maximum matching, so there is an $N$-augmenting path and therefore there is an $N'$ such that $|N'| = |N|+1$.
I think I can see $N= M'$ and $M=N'$ but I don't know how to prove it formally.
Let call $T$ to $G[MDelta N]=Mcup N−Mcup N$ Which each vertex in $T$ has a degree either one or two. Also, any component of $T$ is either an even cycle or a path with edges alternately in $M$ and $N$, where at least one path have starting and ending in $M$ because of the condition $|M|> |N|$.
P.D. Some modifications of the question have been done according to the hints given by @LeenDroogendijk
graph-theory
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
$endgroup$
I'm studying for a test in Graph Theory and I don't know how to prove that Union and intersection part of the following exercise:
Let $M$ and $N$ be matchings in a graph $G$ with $|M|>|N|$. Then there exist matchings $M'$ and $N'$ in $G$ such that $|M'|=|M|-1, |N'|=|N|+1, M' cap N' = M cap N$ and $M' cup N'=M cup N$.
What I have until now:
I know that as $|M| > |N|$ then $N$ is not a maximum matching, so there is an $N$-augmenting path and therefore there is an $N'$ such that $|N'| = |N|+1$.
I think I can see $N= M'$ and $M=N'$ but I don't know how to prove it formally.
Let call $T$ to $G[MDelta N]=Mcup N−Mcup N$ Which each vertex in $T$ has a degree either one or two. Also, any component of $T$ is either an even cycle or a path with edges alternately in $M$ and $N$, where at least one path have starting and ending in $M$ because of the condition $|M|> |N|$.
P.D. Some modifications of the question have been done according to the hints given by @LeenDroogendijk
graph-theory
graph-theory
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
edited Jan 15 at 19:02
Arnaud D.
15.9k52443
15.9k52443
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
asked Jan 15 at 2:49
John HernandezJohn Hernandez
205
205
1
$begingroup$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32
add a comment |
1
$begingroup$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32
1
1
$begingroup$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
HINT: consider the subgraph $H$ of $G$ induced by the edges of $Mcup N$.
Note that the edges that belong to $Mcap N$ are "isolated edges" in $H$.
What can you say about the degree of the vertices of $H$?
What do the connected components of this graph look like?
Now use the fact that $|M|>|N|$.
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
|
show 1 more 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%2f3074026%2fconstructing-a-pair-of-matchings-with-needed-characteristics%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
$begingroup$
HINT: consider the subgraph $H$ of $G$ induced by the edges of $Mcup N$.
Note that the edges that belong to $Mcap N$ are "isolated edges" in $H$.
What can you say about the degree of the vertices of $H$?
What do the connected components of this graph look like?
Now use the fact that $|M|>|N|$.
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
|
show 1 more comment
$begingroup$
HINT: consider the subgraph $H$ of $G$ induced by the edges of $Mcup N$.
Note that the edges that belong to $Mcap N$ are "isolated edges" in $H$.
What can you say about the degree of the vertices of $H$?
What do the connected components of this graph look like?
Now use the fact that $|M|>|N|$.
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
|
show 1 more comment
$begingroup$
HINT: consider the subgraph $H$ of $G$ induced by the edges of $Mcup N$.
Note that the edges that belong to $Mcap N$ are "isolated edges" in $H$.
What can you say about the degree of the vertices of $H$?
What do the connected components of this graph look like?
Now use the fact that $|M|>|N|$.
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
HINT: consider the subgraph $H$ of $G$ induced by the edges of $Mcup N$.
Note that the edges that belong to $Mcap N$ are "isolated edges" in $H$.
What can you say about the degree of the vertices of $H$?
What do the connected components of this graph look like?
Now use the fact that $|M|>|N|$.
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 15 at 6:39
Leen DroogendijkLeen Droogendijk
6,1351716
6,1351716
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
|
show 1 more comment
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
I can say that for all v in H, the deg (v) = 2. I know that $T=G [M Delta N]= M cup N - M cap N $ Which each vertex in T has a degree either one or two. Also, any component of T is either an even cycle or a path with edges alternately in M and N (starting and ending in M). @LeenDroogendijk
$endgroup$
– John Hernandez
Jan 15 at 7:04
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Not quite. Every vertex in $H$ has degree at most $2$. Also the edges of a path do not need to start and end in $M$, but there must be at least one path for which this is true (why?).
$endgroup$
– Leen Droogendijk
Jan 15 at 7:19
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Because |M| > |N|...
$endgroup$
– John Hernandez
Jan 15 at 7:49
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
$begingroup$
Yes, can you complete the proof now?
$endgroup$
– Leen Droogendijk
Jan 15 at 8:50
1
1
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
$begingroup$
On one path you find that has both end-edges in $M$ (or whose only edge is in $M$) you swap the edges between $M$ and $N$. Then you are done.
$endgroup$
– Leen Droogendijk
Jan 15 at 17:44
|
show 1 more 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%2f3074026%2fconstructing-a-pair-of-matchings-with-needed-characteristics%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$
what have you tried?
$endgroup$
– gt6989b
Jan 15 at 2:54
$begingroup$
Yes, for example, I know that as |M| > |N| then N is not a maximum matching, so there is an N-augmenting path and therefore there is an N' s.t. |N'| = |N|+1. I think I can see N= M' and M=N' but I don't know how to prove it formally.
$endgroup$
– John Hernandez
Jan 15 at 3:32