Fix a positive integer $n$ and a finite graph with at least one edge; the endpoints of each edge are distinct, and any two vertices are joined by at most one edge. Vertices and edges are assigned (not necessarily distinct) numbers in the range from $0$ to $n-1$, one number each. A vertex assignment and an edge assignment are compatible if the following condition is satisfied at each vertex $v$: The number assigned to $v$ is congruent modulo $n$ to the sum of the numbers assigned to the edges incident to $v$. Fix a vertex assignment and let $N$ be the total number of compatible edge assignments; compatibility refers, of course, to the fixed vertex assignment. Prove that, if $N \neq 0$, then the prime divisors of $N$ are all at most $n$.
Problem
Source: RMM Extralist 2021 C2
Tags: RMM Shortlist, graph theory, weights, combinatorics
Phorphyrion
19.09.2023 10:16
By CRT, $N(n)$ is equal to the product of $N(p^k)$ for all full prime powers $p^k\mid n$ (where to calculate this number we reduce the fixed vertex labelling mod $p^k$). The set of differences between compatible labellings lie in a subgroup of $(\mathbb{Z} /p^k) ^E$ of size $N(p^k)\neq 0$, cut out by the condition that the sum around each vertex is $0$ (there is a bijection from the compatible labellings to the set of differences by $s\mapsto s-s_0$ for some fixed compatible labelling $s_0$). Writing this subgroup as a product of cyclic groups, we must have all factors of size a power of $p$, as the orders of all elements are powers of $p$ in the original group. Thus $N(p^k) $ is a power of $p$ and we're done.
dgrozev
22.09.2023 19:01
Phorphyrion wrote: By CRT, $N(n)$ is equal to the product of $N(p^k)$ for all full prime powers $p^k\mid n$ (where to calculate this number we reduce the fixed vertex labelling mod $p^k$).... I'm not sure how you can use CRT on some product space $\left(\mathbb{Z}/n\mathbb{Z}\right)^{|E|}$ as you project it on $\left(\mathbb{Z}/p^k\mathbb{Z}\right)^{|E|}$. But this is not important, since you does not need to consider $N(p^k)$. You can do your argument in the same way without it. As you noticed $s-s_0$ as $s$ runs through all compatible labeling is a sugroup of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{|E|}$, so its order must divide $n^{|E|}$ and the result follows.
Number1048576
01.02.2024 20:19
Split the graph into vertex-disjoint connected components; note that we are done if we can prove the statement for one of these connected components. If $X$ is a vertex or edge, let $L(X)$ be its label.
We will prove the following key lemma by induction on the number of edges of a connected component:
Lemma: an edge assignment is compatible always if $n$ is odd and the graph is not bipartite, when the sum of the numbers assigned to the vertices is even if $n$ is even and the graph is not bipartite, and when the sum of the numbers assigned to the vertices of one colour is congruent to the sum of the numbers assigned to vertices of the other colour $\bmod n$ if the graph is bipartite, and furthermore $N$ is independent of the numbers assigned to the vertices.
Base:
There is only one (bipartite) graph with one edge - then we clearly must have that the two vertices have equal numbers assigned to them, and there is exactly one way to assign a number to the edge in this case.
The smallest non-bipartite graph $G$ is a $3$-cycle $V_1V_2V_3$. If we label edge $V_1V_2$ $x$, then the problem is reduced to finding a labelling for $G-E$ where we subtract $x$ from $L(V_1)$ and $L(V_2)$. However, we must now label edge $V_1V_3$ $L(V_1) - x$, and we must label edge $V_2V_3$ $L(V_2) - x$, so we need $L(V_1)+L(V_2) - 2x \equiv L(V_3) \pmod n$. If $n$ is odd, such an $x$ exists and there is exactly one, so there is exactly one way to label the edges regardless of the vertices' labels. If $n$ is even, there are exactly two such $x$ if and only if $L(V_1)+L(V_2)+L(V_3) \equiv 0 \pmod 2$, and otherwise there are no such $x$, so if the sum of the labels of the vertices is even the number of edge labellings is independent of the labels, proving the base case.
Step:
First, note that in a connected graph either there is a vertex of degree $1$ or there is a cycle, in which case if we remove an edge from that cycle the graph is still connected.
Note that in a bipartite graph the sum of the labels of the edges is congruent to the sum of the labels of vertices of one colour and the sum of the labels of vertices of the other colour, so those two sums must be congruent to each other.
Now, if the graph $G$ is bipartite and there is a vertex $V_1$ of degree $1$ with edge $V_1V_2$, there is exactly one label it can be. Then if we remove $E$ and subtract $V_2$ by $L(V_1)$, the sums of the labels of vertices of the two colours are the same, so by induction there is a way to assign numbers to the edges which works, and the number of ways of doing this is independent of the vertex labels.
If there is no vertex of degree $1$, pick an edge in a cycle, label it with any number and remove it, subtracting its value from the labels of the two neighbours. Then the equal sum condition is still satisfied and the graph is still connected, so there is an assignment and the number of ways of making this assignment is independent of the vertex labels, so the number of assignments of the original graph is $n$ times the number of assignments of this graph.
On the other hand, if the graph is not bipartite, as before if there is a vertex of degree $1$, it can only have one label, which we assign to it before removing the edge and subtracting the other vertex it is connected to's label by the value we assign. Note that in this case the parity of the sum of the vertices is unchanged if $n$ is even. Hence, if the resulting graph isn't bipartite then we are done by the inductive hypothesis, but the resulting graph cannot be bipartite as if it was we can just make the colour of the vertex we removed the opposite colour to the vertex it was connected to so the original graph would also be bipartite.
If on the other hand there is no vertex of degree $1$, pick an edge in a cycle.
If removing it results in a non-bipartite graph, then we can just label it any way we want and are done by the inductive hypothesis. If on the other hand removing it results in a bipartite graph, it must have been connected two vertices of the same colour. Then if $n$ is odd there is exactly one way of choosing it so that the sum condition holds, and exactly two ways if $n$ is even and the total sum of the labels of the vertices is even. Either way, the number of ways of labelling the edges is independent of the labels of the vertices by the inductive hypothesis, completing the induction.
Now, we prove the problem statement by induction on the number of edges. The base case is clear, and for the step case note that every time we removed an edge in the previous argument there were either $1$, $2$ or $n$ ways to label it, and so the number of ways of labelling the edges on a general graph is of the form $2^an^b$ if it is possible, and so we are done.