Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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...

share|improve this question
1  
It can’t be disconnected. Neither can a graph with a Hamilton circuit. – Brian M. Scott Apr 11 '12 at 1:26
Maybe you should ask your colleague to exhibit the graph. – Rahul Narain Apr 11 '12 at 1:27
It might be a trick question with a silly answer like "empty graph". Depending on the definition the empty graph might be a disconnected one, e.g. if disconnected is defined as $\forall v \in V.\ \exists x, y \in V.\ x$ and $y$ are not connected. I do know that such definition does not make sense, just giving an example. – dtldarek Apr 11 '12 at 1:40
@dtldarek, good point! There are good reasons to consider the empty graph disconnected. But I have no idea if it qualifies as Eulerian, Hamiltonian, or bipartite. – Rahul Narain Apr 11 '12 at 2:02

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
But the cycle of four vertices isn't a bipartite graph, isn't it ? – Pacane Apr 11 '12 at 3:31
Sure it is. ${}$ – Gerry Myerson Apr 11 '12 at 4:17
@Pacane Label the vertices in order around the cycle $A$, $B$, $C$, and $D$. The sets $\{A, C\}$ and $\{B, D\}$ are a bipartition. – Austin Mohr Apr 11 '12 at 12:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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