# Whose full bipartite and 3-partite graphs are eulerian/hamiltonian graphs?

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?

-
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

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.

-

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.

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