I am trying to write simple induction on below Observation, but I am not sure if I am writing it correctly. Thank you for your advice! Note that we can move each agent only once.
Observation 1: If we have graph with agents and we move agents in $k$ steps, where $k > 0$ created graph will never be the same as the starting graph. Agents can only move to empty nodes of the graph and there is at least one empty node.
Proof:
We proof this by induction. Let us have an assignment $\mathbf{v}$ on initial graph $G_0$ and number of jumps $n$. We denote agent movement in $i$-th graph as $G_i + jump = G_{i + 1}$.
Base case: When $n = 1$, our observation is true as after one jump agent vacates some node in $G_0$ and moves to new node. Following our predefined agent movement we can write this as $G_0 + jump = G_1$.
Induction step: Let $k \in \mathbb{N}_+$ and suppose that Observation 1 is true for $n = k$. Then
$$G_{k + 1} = G_{k} + jump$$
$$ G_{k+1} = G_{k - 1} + jump + jump \text{ (by induction hypothesis)}$$
Thus, Observation 1 holds for $n = k + 1$.
**Conclusion: By the principle of induction, Observation 1 is true for all $n \in \mathbb{N}_+$.