A Graph G where each vertex has an even degree can be split into cycles by which no cycle has a common edge.
$begingroup$
According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ?
Here is the link in which it was proved, but i couldn't understand for the above scenario
http://mathonline.wikidot.com/euler-s-theorem (lemma-2 in this link)
graph-theory eulerian-path
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
$endgroup$
add a comment |
$begingroup$
According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ?
Here is the link in which it was proved, but i couldn't understand for the above scenario
http://mathonline.wikidot.com/euler-s-theorem (lemma-2 in this link)
graph-theory eulerian-path
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
$endgroup$
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43
add a comment |
$begingroup$
According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ?
Here is the link in which it was proved, but i couldn't understand for the above scenario
http://mathonline.wikidot.com/euler-s-theorem (lemma-2 in this link)
graph-theory eulerian-path
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
$endgroup$
According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ?
Here is the link in which it was proved, but i couldn't understand for the above scenario
http://mathonline.wikidot.com/euler-s-theorem (lemma-2 in this link)
graph-theory eulerian-path
graph-theory eulerian-path
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
asked Jan 9 at 4:37
Madhu AvinashMadhu Avinash
1011
1011
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43
add a comment |
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles.
By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
add a comment |
$begingroup$
Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.
This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,ldots, C_{m}$. But then $C, C_0, ldots, C_m$ is a partitioning of $E(G)$ into cycles.
answered Jan 9 at 17:16
MikeMike
4,171412
$endgroup$
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%2f3067070%2fa-graph-g-where-each-vertex-has-an-even-degree-can-be-split-into-cycles-by-which%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles.
By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
add a comment |
$begingroup$
The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles.
By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
add a comment |
$begingroup$
The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles.
By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles.
By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 9 at 15:15
Leen DroogendijkLeen Droogendijk
6,1351716
6,1351716
add a comment |
add a comment |
$begingroup$
Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.
This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,ldots, C_{m}$. But then $C, C_0, ldots, C_m$ is a partitioning of $E(G)$ into cycles.
answered Jan 9 at 17:16
MikeMike
4,171412
$endgroup$
add a comment |
$begingroup$
Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.
This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,ldots, C_{m}$. But then $C, C_0, ldots, C_m$ is a partitioning of $E(G)$ into cycles.
answered Jan 9 at 17:16
MikeMike
4,171412
$endgroup$
add a comment |
$begingroup$
Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.
This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,ldots, C_{m}$. But then $C, C_0, ldots, C_m$ is a partitioning of $E(G)$ into cycles.
answered Jan 9 at 17:16
MikeMike
4,171412
$endgroup$
Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.
This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,ldots, C_{m}$. But then $C, C_0, ldots, C_m$ is a partitioning of $E(G)$ into cycles.
answered Jan 9 at 17:16
MikeMike
4,171412
answered Jan 9 at 17:16
MikeMike
4,171412
answered Jan 9 at 17:16
MikeMike
4,171412
answered Jan 9 at 17:16
MikeMike
4,171412
4,171412
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%2f3067070%2fa-graph-g-where-each-vertex-has-an-even-degree-can-be-split-into-cycles-by-which%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
$begingroup$
Note that the mentioned statement never specified the size of cycles.
$endgroup$
– Ivan Neretin
Jan 9 at 9:43