We study sharp $p$-variational inequalities for the Hardy-Littlewood maximal operator on complete graphs, answering in the affirmative a question by Feng Liu and Qingying Xue. We also use computational assistance to find sharp constants in $1$-variational inequalities for all connected graphs on at most five vertices and pose a conjecture on the corresponding sharp constants for path graphs. Finally, we construct finite graphs with arbitrarily large $p$-variational constants.