A graph with a disjoint matching contains components that are either paths or even circuits.
$begingroup$
I wish to prove the following result:
Let $M$ and $M'$ be disjoint matchings in a graph $G = (V,E)$. Show that every component
of the graph $(V, M cup M')$ is a path or an even circuit.
We just started learning about matchings, which is a set of edges that pairwise have no endpoint in common. Formally it means that if $M$ is a matching, we know that $M subseteq E$ and for $e, e' in M$ it holds that $e cap e'= emptyset$.
Now I need to make some sort of disctinction for union of two of these matchings $M$ and $M'$, such that $M cap M '= emptyset$. I do not see what kind of distinction to make, I also feel a little bit overwhelmed by the "every component" part. It feels very general. Can somebody offer a useful hint, how to proceed/start a good distinction? Basically what I think I need to do is show that if $C$ is a circuit, it has to be even.
scrap paper:
Suppose we colour matching $M$ blue and we colour matching $M'$ red. Then the idea is that for an even circuit, these two colours alternate.
graph-theory matching-theory
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
$endgroup$
add a comment |
$begingroup$
I wish to prove the following result:
Let $M$ and $M'$ be disjoint matchings in a graph $G = (V,E)$. Show that every component
of the graph $(V, M cup M')$ is a path or an even circuit.
We just started learning about matchings, which is a set of edges that pairwise have no endpoint in common. Formally it means that if $M$ is a matching, we know that $M subseteq E$ and for $e, e' in M$ it holds that $e cap e'= emptyset$.
Now I need to make some sort of disctinction for union of two of these matchings $M$ and $M'$, such that $M cap M '= emptyset$. I do not see what kind of distinction to make, I also feel a little bit overwhelmed by the "every component" part. It feels very general. Can somebody offer a useful hint, how to proceed/start a good distinction? Basically what I think I need to do is show that if $C$ is a circuit, it has to be even.
scrap paper:
Suppose we colour matching $M$ blue and we colour matching $M'$ red. Then the idea is that for an even circuit, these two colours alternate.
graph-theory matching-theory
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
$endgroup$
add a comment |
$begingroup$
I wish to prove the following result:
Let $M$ and $M'$ be disjoint matchings in a graph $G = (V,E)$. Show that every component
of the graph $(V, M cup M')$ is a path or an even circuit.
We just started learning about matchings, which is a set of edges that pairwise have no endpoint in common. Formally it means that if $M$ is a matching, we know that $M subseteq E$ and for $e, e' in M$ it holds that $e cap e'= emptyset$.
Now I need to make some sort of disctinction for union of two of these matchings $M$ and $M'$, such that $M cap M '= emptyset$. I do not see what kind of distinction to make, I also feel a little bit overwhelmed by the "every component" part. It feels very general. Can somebody offer a useful hint, how to proceed/start a good distinction? Basically what I think I need to do is show that if $C$ is a circuit, it has to be even.
scrap paper:
Suppose we colour matching $M$ blue and we colour matching $M'$ red. Then the idea is that for an even circuit, these two colours alternate.
graph-theory matching-theory
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
$endgroup$
I wish to prove the following result:
Let $M$ and $M'$ be disjoint matchings in a graph $G = (V,E)$. Show that every component
of the graph $(V, M cup M')$ is a path or an even circuit.
We just started learning about matchings, which is a set of edges that pairwise have no endpoint in common. Formally it means that if $M$ is a matching, we know that $M subseteq E$ and for $e, e' in M$ it holds that $e cap e'= emptyset$.
Now I need to make some sort of disctinction for union of two of these matchings $M$ and $M'$, such that $M cap M '= emptyset$. I do not see what kind of distinction to make, I also feel a little bit overwhelmed by the "every component" part. It feels very general. Can somebody offer a useful hint, how to proceed/start a good distinction? Basically what I think I need to do is show that if $C$ is a circuit, it has to be even.
scrap paper:
Suppose we colour matching $M$ blue and we colour matching $M'$ red. Then the idea is that for an even circuit, these two colours alternate.
graph-theory matching-theory
graph-theory matching-theory
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
edited Dec 4 '18 at 17:06
Wesley Strik
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
asked Dec 4 '18 at 16:46
Wesley StrikWesley Strik
1,635423
1,635423
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Edges in $M$ do not intersect and edges in $M'$ do not intersect either. The only way edges in $(V(G),Mcup M')$ can intersect is between edges in $M$ and edges in $M'$. We can't have three edges intersect at the same vertex. That is because two of those edges both belong to either $M$ or $M'$, But they can't intersect by definition of a matching. Hence the degree of each vertex in $(V(G),Mcup M')$ is at most two. Hence vertices in each components is at most 2. So then that means the component is either a path or a cycle.
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
|
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%2f3025813%2fa-graph-with-a-disjoint-matching-contains-components-that-are-either-paths-or-ev%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$
Edges in $M$ do not intersect and edges in $M'$ do not intersect either. The only way edges in $(V(G),Mcup M')$ can intersect is between edges in $M$ and edges in $M'$. We can't have three edges intersect at the same vertex. That is because two of those edges both belong to either $M$ or $M'$, But they can't intersect by definition of a matching. Hence the degree of each vertex in $(V(G),Mcup M')$ is at most two. Hence vertices in each components is at most 2. So then that means the component is either a path or a cycle.
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
|
show 1 more comment
$begingroup$
Edges in $M$ do not intersect and edges in $M'$ do not intersect either. The only way edges in $(V(G),Mcup M')$ can intersect is between edges in $M$ and edges in $M'$. We can't have three edges intersect at the same vertex. That is because two of those edges both belong to either $M$ or $M'$, But they can't intersect by definition of a matching. Hence the degree of each vertex in $(V(G),Mcup M')$ is at most two. Hence vertices in each components is at most 2. So then that means the component is either a path or a cycle.
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
$endgroup$
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
|
show 1 more comment
$begingroup$
Edges in $M$ do not intersect and edges in $M'$ do not intersect either. The only way edges in $(V(G),Mcup M')$ can intersect is between edges in $M$ and edges in $M'$. We can't have three edges intersect at the same vertex. That is because two of those edges both belong to either $M$ or $M'$, But they can't intersect by definition of a matching. Hence the degree of each vertex in $(V(G),Mcup M')$ is at most two. Hence vertices in each components is at most 2. So then that means the component is either a path or a cycle.
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
$endgroup$
Edges in $M$ do not intersect and edges in $M'$ do not intersect either. The only way edges in $(V(G),Mcup M')$ can intersect is between edges in $M$ and edges in $M'$. We can't have three edges intersect at the same vertex. That is because two of those edges both belong to either $M$ or $M'$, But they can't intersect by definition of a matching. Hence the degree of each vertex in $(V(G),Mcup M')$ is at most two. Hence vertices in each components is at most 2. So then that means the component is either a path or a cycle.
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
edited Dec 4 '18 at 17:02
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
answered Dec 4 '18 at 16:57
nafhgoodnafhgood
1,803422
1,803422
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
|
show 1 more comment
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
1
1
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
$M$ and $M'$ are set of edges, $M cap M'= emptyset$ means no edges in common between the two set of edges, but they could still share a same vertex.
$endgroup$
– nafhgood
Dec 4 '18 at 17:02
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
That makes sense.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:07
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
I'm going to continue thinking for a while how to formalise that such a cycle/circuit needs to be an even circuit. I mean if it were of odd length, it would end at the same colour as it would start. Consider a triangle as an example, we start red, blue, red. This is not a matching.
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:09
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
$begingroup$
Oh , that's precisely the argument. If it is of odd length we run into a problem because it violates it being a matching. It really HAS to alternate between the two. It's actually the same argument as for a vertex of degree 3. We cannot have two edges belonging to the same matching meet at the same vertex!
$endgroup$
– Wesley Strik
Dec 4 '18 at 17:11
1
1
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
$begingroup$
you cannot bicolor an odd cycle
$endgroup$
– nafhgood
Dec 4 '18 at 17:12
|
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%2f3025813%2fa-graph-with-a-disjoint-matching-contains-components-that-are-either-paths-or-ev%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
