For $a \geq 1$, determine whether $K_{a,2a,3a}$ or $K_{a,2a,3a+1}$ are Hamiltonian.
I have tried drawing lots of pictures all day but cannot solve the problem. Can someone please help me out with this? I know that there are some results on determining whether a graph is Hamiltonian that are all present in my textbook. For example I know $k(G - S) \leq |S|$ holds for a Hamiltonian graph for every proper set $S$ of vertices.
There are a few other results that I have but I don't know if they are helpful in this problem.
Note: $K_{a, b, c}$ is the complete tripartite graph on $a + b + c$ vertices.
In the case of $K_{a,2a,3a}$, let the $3$ parts be $U,V,W,$ with $|U|=a, |V|=2a, |W|=3a$. Arrange the vertices of $W$ in a circle. Between any two of them, place a vertex from $U\cup V$. This construction gives a Hamilton cycle.
In the case of $K_{a,2a,3a+1}$, suppose there is a Hamilton cycle. Let the parts be $U,V,W,$ with $|U|=a$, $|V|=2a$, $|W|=3a+1$. In the cycle, each vertex from $W$ is adjacent to $2$ vertices from $U\cup V$, giving $6a+2$ vertices in $U\cup V$. Each vertex in $U\cup V$ is counted at most twice, so there are at least $3a+1$ vertices in $U\cup V$, contradiction.