When does the complete bipartite graph K n,m have an Euler Trail(Path)?
up vote
1
down vote
favorite
So I know that an Euler trail must have no more than two odd degree vertices.
So does this mean that either $n$ or $m$ must be odd? Or is it $n = m + 1$?
proof-verification graph-theory bipartite-graph eulerian-path
edited Nov 19 at 10:15
Especially Lime
21.3k22656
asked Nov 19 at 10:05
johntc121
194
add a comment |
up vote
1
down vote
favorite
So I know that an Euler trail must have no more than two odd degree vertices.
So does this mean that either $n$ or $m$ must be odd? Or is it $n = m + 1$?
proof-verification graph-theory bipartite-graph eulerian-path
edited Nov 19 at 10:15
Especially Lime
21.3k22656
asked Nov 19 at 10:05
johntc121
194
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
So I know that an Euler trail must have no more than two odd degree vertices.
So does this mean that either $n$ or $m$ must be odd? Or is it $n = m + 1$?
proof-verification graph-theory bipartite-graph eulerian-path
edited Nov 19 at 10:15
Especially Lime
21.3k22656
asked Nov 19 at 10:05
johntc121
194
So I know that an Euler trail must have no more than two odd degree vertices.
So does this mean that either $n$ or $m$ must be odd? Or is it $n = m + 1$?
proof-verification graph-theory bipartite-graph eulerian-path
proof-verification graph-theory bipartite-graph eulerian-path
edited Nov 19 at 10:15
Especially Lime
21.3k22656
asked Nov 19 at 10:05
johntc121
194
edited Nov 19 at 10:15
Especially Lime
21.3k22656
asked Nov 19 at 10:05
johntc121
194
edited Nov 19 at 10:15
Especially Lime
21.3k22656
edited Nov 19 at 10:15
Especially Lime
21.3k22656
edited Nov 19 at 10:15
Especially Lime
21.3k22656
21.3k22656
asked Nov 19 at 10:05
johntc121
194
asked Nov 19 at 10:05
johntc121
194
asked Nov 19 at 10:05
johntc121
194
194
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
You're right that it has an Euler trail if and only if the number of odd-degree vertices is at most $2$.
In $K_{m,n}$ there are $m$ vertices of degree $n$ and $n$ vertices of degree $n$.
If $m,n$ are both even then all degrees are even so there is an Euler trail.
If exactly one of them, say $m$, is odd then there are $n$ vertices of odd degree. So when can there be an Euler trail in this case?
If $m,n$ are both odd then there are $m+n$ odd degree vertices. When does this give an Euler trail?
answered Nov 19 at 10:14
Especially Lime
21.3k22656
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
You're right that it has an Euler trail if and only if the number of odd-degree vertices is at most $2$.
In $K_{m,n}$ there are $m$ vertices of degree $n$ and $n$ vertices of degree $n$.
If $m,n$ are both even then all degrees are even so there is an Euler trail.
If exactly one of them, say $m$, is odd then there are $n$ vertices of odd degree. So when can there be an Euler trail in this case?
If $m,n$ are both odd then there are $m+n$ odd degree vertices. When does this give an Euler trail?
answered Nov 19 at 10:14
Especially Lime
21.3k22656
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
add a comment |
up vote
2
down vote
accepted
You're right that it has an Euler trail if and only if the number of odd-degree vertices is at most $2$.
In $K_{m,n}$ there are $m$ vertices of degree $n$ and $n$ vertices of degree $n$.
If $m,n$ are both even then all degrees are even so there is an Euler trail.
If exactly one of them, say $m$, is odd then there are $n$ vertices of odd degree. So when can there be an Euler trail in this case?
If $m,n$ are both odd then there are $m+n$ odd degree vertices. When does this give an Euler trail?
answered Nov 19 at 10:14
Especially Lime
21.3k22656
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
You're right that it has an Euler trail if and only if the number of odd-degree vertices is at most $2$.
In $K_{m,n}$ there are $m$ vertices of degree $n$ and $n$ vertices of degree $n$.
If $m,n$ are both even then all degrees are even so there is an Euler trail.
If exactly one of them, say $m$, is odd then there are $n$ vertices of odd degree. So when can there be an Euler trail in this case?
If $m,n$ are both odd then there are $m+n$ odd degree vertices. When does this give an Euler trail?
answered Nov 19 at 10:14
Especially Lime
21.3k22656
You're right that it has an Euler trail if and only if the number of odd-degree vertices is at most $2$.
In $K_{m,n}$ there are $m$ vertices of degree $n$ and $n$ vertices of degree $n$.
If $m,n$ are both even then all degrees are even so there is an Euler trail.
If exactly one of them, say $m$, is odd then there are $n$ vertices of odd degree. So when can there be an Euler trail in this case?
If $m,n$ are both odd then there are $m+n$ odd degree vertices. When does this give an Euler trail?
answered Nov 19 at 10:14
Especially Lime
21.3k22656
answered Nov 19 at 10:14
Especially Lime
21.3k22656
answered Nov 19 at 10:14
Especially Lime
21.3k22656
answered Nov 19 at 10:14
Especially Lime
21.3k22656
21.3k22656
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
add a comment |
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
So does this mean that there are two possiblities for the odd occurence? Ie... n = m =1? and n =2 and m = odd number >= 1?
– johntc121
Nov 19 at 10:30
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
@johntc121 yes, that's exactly right (of course you can also swap $m$ and $n$ in the second case).
– Especially Lime
Nov 19 at 10:49
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
Awesome. Thank you so much
– johntc121
Nov 19 at 16:13
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3004736%2fwhen-does-the-complete-bipartite-graph-k-n-m-have-an-euler-trailpath%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
