Proving that we can construct an Euler trail in an undirected graph G, iff G is connected and has exactly two...
$begingroup$
I'm having trouble proving the following:
If G is an undirected graph with no isolated vertices, then we can construct an Euler trail in G if and only if G is connected and has exactly two vertices of odd degree.
discrete-mathematics graph-theory
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
$endgroup$
add a comment |
$begingroup$
I'm having trouble proving the following:
If G is an undirected graph with no isolated vertices, then we can construct an Euler trail in G if and only if G is connected and has exactly two vertices of odd degree.
discrete-mathematics graph-theory
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
$endgroup$
1
$begingroup$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49
add a comment |
$begingroup$
I'm having trouble proving the following:
If G is an undirected graph with no isolated vertices, then we can construct an Euler trail in G if and only if G is connected and has exactly two vertices of odd degree.
discrete-mathematics graph-theory
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
$endgroup$
I'm having trouble proving the following:
If G is an undirected graph with no isolated vertices, then we can construct an Euler trail in G if and only if G is connected and has exactly two vertices of odd degree.
discrete-mathematics graph-theory
discrete-mathematics graph-theory
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
asked Dec 8 '18 at 22:56
Ray BradbaryRay Bradbary
6
6
1
$begingroup$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49
add a comment |
1
$begingroup$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49
1
1
$begingroup$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
$endgroup$
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
add a comment |
$begingroup$
An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.
Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
$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%2f3031764%2fproving-that-we-can-construct-an-euler-trail-in-an-undirected-graph-g-iff-g-is%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$
Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
$endgroup$
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
add a comment |
$begingroup$
Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
$endgroup$
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
add a comment |
$begingroup$
Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
$endgroup$
Suppose $G$ has a Euler trail, then $G$ is connected. And except the start and end vertices of the trail, all vertices are of even degree(as you go into an intermediate vertex and you leave it). Now, suppose $G$ is a connected graph with exactly 2 vertices of odd degree. Then start a trail from one of the vertex with odd degree(Now you can think of that vertex as a vertex of even degree), and as you go through the vertices along the trail, you can always leave a vertex if they have even degrees or the vertex you started your trail from. You can only get stuck when you visit the other vertex of odd degree. If you end up stuck and hasen't visit all edges yet, then there must be an edge not visited yet and that is connected to a vertex $v$ in your current trail. Then start from $v$ and make another trail that tries to visit all the un-visited edges, you can get stuck only at $v$ . After that, join this trail to the previous one. repeat this same process if there is edges not visited yet by the trail. So then at the end, that gives an Euler trail(It is called the Hierholzer's algorithm for finding Euler trail). Is this correct?
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
edited Dec 10 '18 at 5:53
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
answered Dec 9 '18 at 16:05
nafhgoodnafhgood
1,805422
1,805422
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
add a comment |
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
1
1
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
This is not quite right. The choice you make along the way matter. Consider a bowtie graph which has one additional vertex connected to one of the non-center vertices. If you do this, you must choose to visit the other cycle when you hit the center vertex, otherwise you'll get stuck without covering the edges.
$endgroup$
– platty
Dec 10 '18 at 5:17
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
$begingroup$
you are right! Thank you!
$endgroup$
– nafhgood
Dec 10 '18 at 5:32
add a comment |
$begingroup$
An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.
Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.
Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.
Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
$endgroup$
An alternative proof to show that any connected graph with all even-degree vertices except for two (say, $u,v$) has an Eulerian trail, using the fact that a connected graph with all even-degree vertices contains an Eulerian tour. The other direction follows fairly easily, as outlined by @mathnoob above.
Add in a new vertex $x$ which only has edges to the two odd-degree vertices $u$ and $v$. This new graph is connected, and only has even-degree vertices. It follows that it has an Eulerian tour. Start from $x$ and follow this Eulerian tour; since there are only two edges incident on $x$, these must be the first and last edges in the tour. Removing $x$ and these two edges then gives an Eulerian trail beginning at $u$ and ending at $v$ or vice versa.
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
answered Dec 12 '18 at 6:54
plattyplatty
3,370320
3,370320
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%2f3031764%2fproving-that-we-can-construct-an-euler-trail-in-an-undirected-graph-g-iff-g-is%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$
This depends on what you can use. Have you already proven that a connected graph with all even-degree vertices contains an Eulerian tour?
$endgroup$
– platty
Dec 9 '18 at 0:22
$begingroup$
yes I have been able to prove it
$endgroup$
– Ray Bradbary
Dec 12 '18 at 6:49