Mixing
Can there be a bipartite graph that has an Eulerian circuit, Hamiltonian cycle, but is nonplanar?
$begingroup$
So far I have that the graph's chromatic number is two (not sure how that would help) as well as that since it has an Eulerian circuit, all vertices must have even degree. I am thinking of using Kuratowski's theorem and showing it has no subgraphs homeomorphic to $K_5$ or $K_{3,3}$ but I am unsure how to do that.
Should I start by showing since it is bipartite all of its subgraphs must be bipartite, hence cannot be homeomorphic to $K_5$ or $K_{3,3}$? Or would that be an incorrect approach? Thanks!
graph-theory
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
$endgroup$
add a comment |
$begingroup$
So far I have that the graph's chromatic number is two (not sure how that would help) as well as that since it has an Eulerian circuit, all vertices must have even degree. I am thinking of using Kuratowski's theorem and showing it has no subgraphs homeomorphic to $K_5$ or $K_{3,3}$ but I am unsure how to do that.
Should I start by showing since it is bipartite all of its subgraphs must be bipartite, hence cannot be homeomorphic to $K_5$ or $K_{3,3}$? Or would that be an incorrect approach? Thanks!
graph-theory
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
$endgroup$
1
$begingroup$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59
add a comment |
$begingroup$
So far I have that the graph's chromatic number is two (not sure how that would help) as well as that since it has an Eulerian circuit, all vertices must have even degree. I am thinking of using Kuratowski's theorem and showing it has no subgraphs homeomorphic to $K_5$ or $K_{3,3}$ but I am unsure how to do that.
Should I start by showing since it is bipartite all of its subgraphs must be bipartite, hence cannot be homeomorphic to $K_5$ or $K_{3,3}$? Or would that be an incorrect approach? Thanks!
graph-theory
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
$endgroup$
So far I have that the graph's chromatic number is two (not sure how that would help) as well as that since it has an Eulerian circuit, all vertices must have even degree. I am thinking of using Kuratowski's theorem and showing it has no subgraphs homeomorphic to $K_5$ or $K_{3,3}$ but I am unsure how to do that.
Should I start by showing since it is bipartite all of its subgraphs must be bipartite, hence cannot be homeomorphic to $K_5$ or $K_{3,3}$? Or would that be an incorrect approach? Thanks!
graph-theory
graph-theory
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
edited Feb 20 at 22:39
Vinyl_cape_jawa
3,33511433
3,33511433
asked Feb 2 at 23:41
EJJJJEJJJJ
456
asked Feb 2 at 23:41
EJJJJEJJJJ
456
asked Feb 2 at 23:41
EJJJJEJJJJ
456
456
1
$begingroup$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59
add a comment |
1
$begingroup$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59
1
1
$begingroup$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m ge 3$ .
answered Feb 3 at 18:21
MikeMike
4,641512
$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%2f3097954%2fcan-there-be-a-bipartite-graph-that-has-an-eulerian-circuit-hamiltonian-cycle%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$
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m ge 3$ .
answered Feb 3 at 18:21
MikeMike
4,641512
$endgroup$
add a comment |
$begingroup$
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m ge 3$ .
answered Feb 3 at 18:21
MikeMike
4,641512
$endgroup$
add a comment |
$begingroup$
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m ge 3$ .
answered Feb 3 at 18:21
MikeMike
4,641512
$endgroup$
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m ge 3$ .
answered Feb 3 at 18:21
MikeMike
4,641512
answered Feb 3 at 18:21
MikeMike
4,641512
answered Feb 3 at 18:21
MikeMike
4,641512
answered Feb 3 at 18:21
MikeMike
4,641512
4,641512
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%2f3097954%2fcan-there-be-a-bipartite-graph-that-has-an-eulerian-circuit-hamiltonian-cycle%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$
Have you made an attempt to find such a graph?
$endgroup$
– Misha Lavrov
Feb 3 at 0:58
$begingroup$
Yes, $K_{4,4}$.
$endgroup$
– W.R.P.S
Feb 3 at 7:59