Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit

430 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.