Moving particles on graph

Solution 1:

If $n$ is a prime number, then there is a solution for every $k\leq n-1$.

Namely, label the vertices of the graph with elements of $\mathbb{Z}/n\mathbb{Z}$ and label the particles in each vertex $1,2,\ldots,k\in\mathbb{Z}/n\mathbb{Z}$. At each step, a particle labeled $p$ currently at vertex $x$ goes to vertex $x+p$.

Since $n$ is prime, in $n$ steps, each particles goes through a Hamiltonian cycle, hence the first requirement is satisfied.

Note (via induction) that at every step, the particles in each vertex have distinct labels. This in particular means that each vertex has at most $k$ particles (hence exactly $k$ particles) at every step. So, the third requirement is fulfilled.

Lastly, suppose that at step $t$ ($0\leq t<n$), two particles labeled $p$ and $q$ (with $p\neq q$) meet at the same position for the first time. Let $(x_s)_{t\leq s<n}$ and $(y_s)_{t\leq s<n}$ denote the trajectories of these two particles from that moment on. Let $z_s:=y_s-x_s$ and $r:=q-p$. Observe that $z_t=0$ and $z_{s+1}=z_s+r$ for $s\geq t$. Since $r$ and $n$ are relatively prime, $z_s\neq 0$ for $t\leq s<n$, which means the two particles will not meet again. Hence, the second requirement is satisfied as well.

So, your father could for instance use $7$ groups with either $5$ or $6$ students in each group. If the groups of $5$ at the beginning are labeled $1,2,\ldots,5$ (so the missing number is $6$), then at every following step, he will still have $5$ or $6$ students at each group with $6$ being the missing number in the groups of $5$.