1
$\begingroup$

A colleague of mine claims that there exists one, but I can't figure how an eulerian graph can be disconnected, since you have to visit all the graph vertices in the cycle...

  • 0
    @dtldarek, good point! [There are good reasons to consider the empty graph disconnected](http://math.stackexchange.com/questions/50551/is-the-empty-graph-connected). But I have no idea if it qualifies as Eulerian, Hamiltonian, or bipartite.2012-04-11

1 Answers 1

2

It's possible that your colleague is using a non-standard definition by saying that the disjoint union of eulerian/hamiltonian connected components is itself eulerian/hamiltonian. If this is the case, then simply considering one connected component of the graph will suffice, and so the problem reduces to showing a connected, hamiltonian, eulerian, bipartite graph. There are many such examples, the cycle on four vertices being the smallest nontrivial example.

  • 0
    @Pacane Label the vertices in order around the cycle $A$, $B$, $C$, and $D$. The sets $\{A, C\}$ and $\{B, D\}$ are a bipartition.2012-04-11