0
$\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:

example of graph with a loop at both start and end vertex

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?

$\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
0
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.