Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Which full bipartite ($K_{r,s}$) and 3-partite ($K_{r,s,t}$) graphs are eulerian/hamiltonian graphs?

What I have found so far:

  1. bipartite/eulerian $\rightarrow 2|r \land 2|s$
  2. $3$-partite/eulerian $\rightarrow 2|r \land 2|s \land 2|t$
  3. bipartite/hamiltonian $\rightarrow r=s$
  4. $3$-partite/hamiltonian $\rightarrow s=r+t$ (and symmetric cases) or $ s=r+t + 1$

Shortly speaking:

$1.$ and $2. $ is a result of the fact that graph has eulerian cycle $\leftrightarrow$ $2|deg(v)$ $ v\in V(G)$

$3.$ and $4.$ we have $k$-partite graphs so when we go to one part, we must be able to return.

Do you agree with that?

share|cite|improve this question
Counterexample to your condition 2) $\forall v\in V(K_{3,3,3}), \,\, 2|\text{deg(v)} \quad \implies \quad K_{3,3,3} \, \text{ is eulerian}$ – Stano Apr 20 '13 at 12:57
up vote 1 down vote accepted

A graph is eulerian iff all its vertex degrees are even. For a complete 3-partite graph $K_{r,s,t}$, this is true if $r + s$, $r+t$, and $s+t$ are all even, which happens iff $r$, $s$, and $t$ are all the same parity.

Ore's theorem implies that a complete 3-partite graph is always hamiltonian unless one part has more than half the vertices. The converse also holds in this case.

share|cite|improve this answer

1) is OK
2) incorrect - $K_{3,3,3}$ is eulerian
3) is OK
4) incorrect - $K_{2,3,5}$ is hamiltonian but don't hold your conditions.
Use Dirac's theorem:
$$(V(G)\geq3) \wedge \left(\forall v\in G: deg(v)\geq\frac{V(G)}{2} \right) \implies G \text{ is hamiltonian}$$ and next try to show that it is also sufficient condition.

share|cite|improve this answer
$K_{2,3,5}$ does satisfy his conditions, since 5 = 2 + 3. But $K_{2,2,2}$ is hamiltonian, and does not. – Kundor Apr 20 '13 at 18:27

Your Answer


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.