Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit The 2019 Stack Overflow Developer Survey Results Are InEuler & Hamiltonian CyclesCan a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?Is there any regular, balanced, connected bipartite graph that does not contain any Hamiltonian cycle?Is it possible disconnected graph has euler circuit?Is it possible for a graph that has a hamiltonian circuit but no a eulerian circuitA bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $delta(G) gt frac k2$ is Hamiltonian.Does this graph with one vertex have an Euler circuit?What is connection between Euler graphs, bipartite graphs and having even number of vertices?Does the graph G' has a Euler circuit?3-connected planar bipartite graph without a Hamiltonian path
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
How can I add encounters in the Lost Mine of Phandelver campaign without giving PCs too much XP?
Is bread bad for ducks?
A female thief is not sold to make restitution -- so what happens instead?
Will it cause any balance problems to have PCs level up and gain the benefits of a long rest mid-fight?
Why couldn't they take pictures of a closer black hole?
Can we generate random numbers using irrational numbers like π and e?
Why didn't the Event Horizon Telescope team mention Sagittarius A*?
Can an undergraduate be advised by a professor who is very far away?
Loose spokes after only a few rides
Is an up-to-date browser secure on an out-of-date OS?
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Why are there uneven bright areas in this photo of black hole?
Match Roman Numerals
Why “相同意思的词” is called “同义词” instead of "同意词"？
Does adding complexity mean a more secure cipher?
Getting crown tickets for Statue of Liberty
Are spiders unable to hurt humans, especially very small spiders?
Pokemon Turn Based battle (Python)
Mathematics of imaging the black hole
Finding the area between two curves with Integrate
Button changing its text & action. Good or terrible?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Why was M87 targeted for the Event Horizon Telescope instead of Sagittarius A*?
Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit
The 2019 Stack Overflow Developer Survey Results Are InEuler & Hamiltonian CyclesCan a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?Is there any regular, balanced, connected bipartite graph that does not contain any Hamiltonian cycle?Is it possible disconnected graph has euler circuit?Is it possible for a graph that has a hamiltonian circuit but no a eulerian circuitA bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $delta(G) gt frac k2$ is Hamiltonian.Does this graph with one vertex have an Euler circuit?What is connection between Euler graphs, bipartite graphs and having even number of vertices?Does the graph G' has a Euler circuit?3-connected planar bipartite graph without a Hamiltonian path
$begingroup$
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, considering that $1$ and $5$ are both connected to themselves? It should still have an Euler circuit and no Hamiltonian circuit.
If we seperated the vertices into sets by color:
$A = 1,3,5$
$B = 2,4$
$1$ and $5$ would not have to be in both sets, but they are still connected to themselves. So if you have a loop at any vertex in a graph, it is automatically not considered bipartite?
graph-theory bipartite-graph hamiltonian-path eulerian-path
edited Apr 8 at 1:39
gt6989b
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
$endgroup$
add a comment |
$begingroup$
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, considering that $1$ and $5$ are both connected to themselves? It should still have an Euler circuit and no Hamiltonian circuit.
If we seperated the vertices into sets by color:
$A = 1,3,5$
$B = 2,4$
$1$ and $5$ would not have to be in both sets, but they are still connected to themselves. So if you have a loop at any vertex in a graph, it is automatically not considered bipartite?
graph-theory bipartite-graph hamiltonian-path eulerian-path
edited Apr 8 at 1:39
gt6989b
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
$endgroup$
$begingroup$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42
add a comment |
$begingroup$
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, considering that $1$ and $5$ are both connected to themselves? It should still have an Euler circuit and no Hamiltonian circuit.
If we seperated the vertices into sets by color:
$A = 1,3,5$
$B = 2,4$
$1$ and $5$ would not have to be in both sets, but they are still connected to themselves. So if you have a loop at any vertex in a graph, it is automatically not considered bipartite?
graph-theory bipartite-graph hamiltonian-path eulerian-path
edited Apr 8 at 1:39
gt6989b
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
$endgroup$
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, considering that $1$ and $5$ are both connected to themselves? It should still have an Euler circuit and no Hamiltonian circuit.
If we seperated the vertices into sets by color:
$A = 1,3,5$
$B = 2,4$
$1$ and $5$ would not have to be in both sets, but they are still connected to themselves. So if you have a loop at any vertex in a graph, it is automatically not considered bipartite?
graph-theory bipartite-graph hamiltonian-path eulerian-path
graph-theory bipartite-graph hamiltonian-path eulerian-path
edited Apr 8 at 1:39
gt6989b
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
edited Apr 8 at 1:39
gt6989b
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
edited Apr 8 at 1:39
gt6989b
35.8k22557
edited Apr 8 at 1:39
gt6989b
35.8k22557
edited Apr 8 at 1:39
gt6989b
35.8k22557
35.8k22557
asked Apr 8 at 1:29
pylabpylab
103
asked Apr 8 at 1:29
pylabpylab
103
asked Apr 8 at 1:29
pylabpylab
103
103
$begingroup$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42
add a comment |
$begingroup$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42
$begingroup$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42
$begingroup$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You are correct. One of the equivalences of $G$ being bipartite is that $G$ has no odd cycles, and a loop is a cycle of size 1.
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
$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%2f3179017%2fgraph-which-is-bipartite-has-an-euler-circuit-but-not-a-hamiltonian-circuit%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$
You are correct. One of the equivalences of $G$ being bipartite is that $G$ has no odd cycles, and a loop is a cycle of size 1.
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
$endgroup$
add a comment |
$begingroup$
You are correct. One of the equivalences of $G$ being bipartite is that $G$ has no odd cycles, and a loop is a cycle of size 1.
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
$endgroup$
add a comment |
$begingroup$
You are correct. One of the equivalences of $G$ being bipartite is that $G$ has no odd cycles, and a loop is a cycle of size 1.
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
$endgroup$
You are correct. One of the equivalences of $G$ being bipartite is that $G$ has no odd cycles, and a loop is a cycle of size 1.
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
answered Apr 8 at 1:41
gt6989bgt6989b
35.8k22557
35.8k22557
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%2f3179017%2fgraph-which-is-bipartite-has-an-euler-circuit-but-not-a-hamiltonian-circuit%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$
This graph also doesn't have an Euler circuit, since $1$ and $5$ have odd degree.
$endgroup$
– Misha Lavrov
Apr 8 at 1:42