Misinterpretation of '1-factorable'
$begingroup$
I am under the impression that I have a simple misunderstanding of some terminology:
A 1-factor is defined to be a 1-regular spanning subgraph. So a 1-factor is a perfect matching. Yet a well-known result states that the Petersen graph is not 1-factorable. However, I can easily identify a perfect matching (many, in fact) of the Petersen graph.
I am assuming 1-factorable means 'possessing a 1-factor', or in other words, a graph is 1-factorable if and only if it has a perfect matching. Where has my terminology gone wrong so as to produce this apparent contradiction? Any assistance would be appreciated.
graph-theory
asked Dec 23 '18 at 20:09
t42dt42d
32
$endgroup$
add a comment |
$begingroup$
I am under the impression that I have a simple misunderstanding of some terminology:
A 1-factor is defined to be a 1-regular spanning subgraph. So a 1-factor is a perfect matching. Yet a well-known result states that the Petersen graph is not 1-factorable. However, I can easily identify a perfect matching (many, in fact) of the Petersen graph.
I am assuming 1-factorable means 'possessing a 1-factor', or in other words, a graph is 1-factorable if and only if it has a perfect matching. Where has my terminology gone wrong so as to produce this apparent contradiction? Any assistance would be appreciated.
graph-theory
asked Dec 23 '18 at 20:09
t42dt42d
32
$endgroup$
2
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59
add a comment |
$begingroup$
I am under the impression that I have a simple misunderstanding of some terminology:
A 1-factor is defined to be a 1-regular spanning subgraph. So a 1-factor is a perfect matching. Yet a well-known result states that the Petersen graph is not 1-factorable. However, I can easily identify a perfect matching (many, in fact) of the Petersen graph.
I am assuming 1-factorable means 'possessing a 1-factor', or in other words, a graph is 1-factorable if and only if it has a perfect matching. Where has my terminology gone wrong so as to produce this apparent contradiction? Any assistance would be appreciated.
graph-theory
asked Dec 23 '18 at 20:09
t42dt42d
32
$endgroup$
I am under the impression that I have a simple misunderstanding of some terminology:
A 1-factor is defined to be a 1-regular spanning subgraph. So a 1-factor is a perfect matching. Yet a well-known result states that the Petersen graph is not 1-factorable. However, I can easily identify a perfect matching (many, in fact) of the Petersen graph.
I am assuming 1-factorable means 'possessing a 1-factor', or in other words, a graph is 1-factorable if and only if it has a perfect matching. Where has my terminology gone wrong so as to produce this apparent contradiction? Any assistance would be appreciated.
graph-theory
graph-theory
asked Dec 23 '18 at 20:09
t42dt42d
32
asked Dec 23 '18 at 20:09
t42dt42d
32
asked Dec 23 '18 at 20:09
t42dt42d
32
asked Dec 23 '18 at 20:09
t42dt42d
32
asked Dec 23 '18 at 20:09
t42dt42d
32
32
2
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59
add a comment |
2
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59
2
2
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A $1$-factor is a $1$-regular spanning subgraph, but a $1$-factorization is a decomposition into edge-disjoint $1$-factors. A graph is $1$-factorable if it has a $1$-factorization.
The Petersen graph has some $1$-factors, but it does not have a $1$-factorization, because once you remove a $1$-factor (a perfect matchings), you will be left with some odd cycles (which do not, themselves, have perfect matchings). So the Petersen graph is not $1$-factorable.
(It does, of course, have a factorization into a $1$-factor and a $2$-factor: a perfect matching and a union of cycles.)
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
$endgroup$
add a comment |
Your Answer
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%2f3050661%2fmisinterpretation-of-1-factorable%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$
A $1$-factor is a $1$-regular spanning subgraph, but a $1$-factorization is a decomposition into edge-disjoint $1$-factors. A graph is $1$-factorable if it has a $1$-factorization.
The Petersen graph has some $1$-factors, but it does not have a $1$-factorization, because once you remove a $1$-factor (a perfect matchings), you will be left with some odd cycles (which do not, themselves, have perfect matchings). So the Petersen graph is not $1$-factorable.
(It does, of course, have a factorization into a $1$-factor and a $2$-factor: a perfect matching and a union of cycles.)
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
$endgroup$
add a comment |
$begingroup$
A $1$-factor is a $1$-regular spanning subgraph, but a $1$-factorization is a decomposition into edge-disjoint $1$-factors. A graph is $1$-factorable if it has a $1$-factorization.
The Petersen graph has some $1$-factors, but it does not have a $1$-factorization, because once you remove a $1$-factor (a perfect matchings), you will be left with some odd cycles (which do not, themselves, have perfect matchings). So the Petersen graph is not $1$-factorable.
(It does, of course, have a factorization into a $1$-factor and a $2$-factor: a perfect matching and a union of cycles.)
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
$endgroup$
add a comment |
$begingroup$
A $1$-factor is a $1$-regular spanning subgraph, but a $1$-factorization is a decomposition into edge-disjoint $1$-factors. A graph is $1$-factorable if it has a $1$-factorization.
The Petersen graph has some $1$-factors, but it does not have a $1$-factorization, because once you remove a $1$-factor (a perfect matchings), you will be left with some odd cycles (which do not, themselves, have perfect matchings). So the Petersen graph is not $1$-factorable.
(It does, of course, have a factorization into a $1$-factor and a $2$-factor: a perfect matching and a union of cycles.)
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
$endgroup$
A $1$-factor is a $1$-regular spanning subgraph, but a $1$-factorization is a decomposition into edge-disjoint $1$-factors. A graph is $1$-factorable if it has a $1$-factorization.
The Petersen graph has some $1$-factors, but it does not have a $1$-factorization, because once you remove a $1$-factor (a perfect matchings), you will be left with some odd cycles (which do not, themselves, have perfect matchings). So the Petersen graph is not $1$-factorable.
(It does, of course, have a factorization into a $1$-factor and a $2$-factor: a perfect matching and a union of cycles.)
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
answered Dec 23 '18 at 22:36
Misha LavrovMisha Lavrov
49.9k759110
49.9k759110
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%2f3050661%2fmisinterpretation-of-1-factorable%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
2
$begingroup$
$1$-factorable means the edge set of the graph is the disjoint union of $1$-factors.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 20:18
$begingroup$
@LordSharktheUnknown Thank you for the clarification.
$endgroup$
– t42d
Dec 24 '18 at 4:59