Hamilton Graph and Complete Tripartite

Question

1) Consider the complete tripartite graph $K_2,_3,_n$ for $n \ge 3$. Determine for what values of n the graph $K_2,_3,_n$ has a Hamilton path, and for what values of n the graph has a Hamilton cycle.

2) Consider the complete tripartite graph $K_2,_m,_n$ for $m \ge 2$ and $n \ge m$. Determine when $K_2,_m,_n$ has a Hamilton and when it has a Hamilton cycle.

I need help on how to go about it. I tried countless number to times on how to set the problem right but to no avail. I would be glad someone offers me assistance on how to answer this problem.

Answer 1

For (1), let's use Ore's Theorem. It states if for every $u, v \in V(G)$ are not adjacent and $d(u) + d(v) \geq n$, then $G$ has a Hamiltonian Circuit. So since $K_{2, 3, m}$ is complete, the only non-adjacent vertices are in each partition. This gives us:

$2(3 + m) \geq 5 + m$, for the elements in the partition of two vertices.
$2(2 + m) \geq 5 + m$, for the elements in the partition of three vertices.
$2(5) \geq 5 + m$ for the elements in the new partition of $m$ vertices.

And so we get $m \geq -1$, $m \geq 1$, and $m \leq 5$ when solving. So $m \in \{1, 2, 3, 4\}$ will answer your question.

Now for a Hamiltonian Path, you want to determine if adding an extra vertex incident to all other vertices will create a Hamiltonian cycle. So $G$ has a Hamiltonian path if and only if $G + K_{1}$ has a Hamiltonian Circuit.

This should get you going in a good direction.

Answer 2

Consider the general tripartite case $G = K_{l,m,n}$ for $1 \leq l \leq m \leq n$. I will show that $K_{l,m,n}$ has a Hamiltonian cycle if and only if $l + m \geq n$.

Suppose $G$ has a Hamiltonian cycle $C$. Then $2n$ edges of $C$ are incident with vertices in the partite set of size $n$, and all $l+m+n$ edges of $C$ are incident with vertices in either the partite set of size $l$ or the partite set of size $m$, or both. Thus $2n \leq l+m+n$, and $l+m \geq n$. We now need only show that there is a Hamiltonian cycle when $l+m \geq n$.

Ore's Theorem states that if $d(u) + d(v) \geq |G|$ for all $u,v \in V(G)$ with $uv \not \in E(G)$, then $G$ has a Hamiltonian cycle. For $K_{l,m,n}$, the only non-adjacent vertices are within the partite sets, so Ore's criterion will be satisfied if each of the following is true:

$2(l + m) \geq l + m + n$

$2(l + n) \geq l + m + n$

$2(m + n) \geq l + m + n$

But since $l + m \leq l + n$ and $l + m \leq m + n$, these will be satisfied if $2(l+m) \geq l + m + n$ and thus $l + m \geq n$. So by Ore's Theorem, if $l + m \geq n$, then $G$ has a Hamiltonian cycle.

For the Hamiltonian path, you can show that $G$ has a Hamiltonian path if and only if the graph $H$ created by adding an extra vertex to $G$ adjacent to all vertices of $G$ has a Hamiltonian cycle. Then by essentially the same argument used above, you can show $H$ has a Hamiltonian cycle if and only $l + m \geq n-1$, and thus $G$ has a Hamiltonian path if and only if $l + m \geq n-1$.