SELECTION and TRAINING SESSION

An edge assignment compatible with a fixed vertex assignment will be referred to as a solution relative to that vertex assignment. A solution relative to the all-zero vertex assignment will be referred to as a fundamental solution; the all-zero edge assignment is a fundamental solution.

Fix a vertex assignment and fix a solution (if any). Componentwise subtraction modulo $n$ of the fixed solution from a solution provides a fundamental solution. Conversely, componentwise addition modulo $n$ of the fixed solution to a fundamental solution provides a solution. The two solution assignments are clearly inverse to one another, so the number of solutions is either zero or equal to the number of fundamental solutions. Consequently, it is sufficient to prove the conclusion for the number $N$ of fundamental solutions.

To this end, induct on the number of edges. The base case is clear: A graph with a single edge has a single fundamental solution, namely, the all zero edge assignment.

For the induction step, consider a graph $G$ with at least two edges. Fix an edge $e$ of $G$ and let $G^{\prime }=G-e$; clearly, $G^{\prime }$ has at least one edge. For each $k$ in the range $0$ through $n-1$, let $S_k$ be the set of fundamental solutions for $G$ assigning $k$ to $e$, and let $T_k$ be the set of solutions for $G^{\prime }$ relative to the vertex assignment sending both end points of $e$ to $n-k$ and all other vertices to zero.

Changing only the $e$-component of a solution in $S_k$ to zero, and changing the vertex assignment only at the end points of $e$ by sending them both to $n-k$, enable removal of $e$ from $G$ to provide a bijection from $S_k$ to $T_k$. Since the size of each non-empty $T_k$ is equal to the number $N^{\prime }$ of fundamental solutions for $G^{\prime }$, so is the size of each non-empty $S_k$. Consequently, $N=m{N}^{\prime }$, where $m$ is the number of non-empty sets $S_k$; incidentally, $m\ge 1$, since $S_0$ is non-empty — it contains the all zero edge assignment. Finally, the prime divisors of $m$ do not exceed $n$, since $m\le n$; and the prime divisors of $N^{\prime }$ do not exceed $n$, by the induction hypothesis. Consequently, the prime divisors of $N=m{N}^{\prime }$ do not exceed $n$ either. This completes the induction step and concludes the proof.