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...
Is there an existing graph that meets the following properties : disconnected, eulerian, hamiltonian and bipartite
1
$\begingroup$
graph-theory
-
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
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