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...
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.