We call a coloring of $3$-regular graph with $3$ colors good if for every $3$ edges incident with a vertex ...

Question

Let $G$ be a $3$-regular graph with $n$ vertices. Color each edge with red, blue or yellow. Now, we call a coloring of graph as good if any three edges incident with any vertex have one color or three colors. Prove that the number of good coloring of $G$ must be a power of $3$.

I have very short solution using linear algebra:

If $M$ is an incidence matrix of this graph and we color each edge with colors $0,1,2$ then we have to find a number of vectors $\vec{c}\in \mathbb{Z}_3^{\varepsilon}$ such that $M\vec{c} =\vec{0} \in \mathbb{Z}_3^{n}$ where $\varepsilon$ is a number of edges $G$. So we are interested in $|\ker(M)|$, but $\ker(M)\leq \mathbb{Z}_3^{\varepsilon}$ and thus $|\ker(M)| = 3^{d}$ where $d=\dim (\ker(M))$.

Even more, we can find exact number of colorings. By handshake lemma we have $\varepsilon = 3n/2$ so $n$ is even and by rank-nullity theorem we have $$ d=\varepsilon -{\rm rank} (M) $$ There is a theorem that says if $G$ is connected then:$${\rm rank}(M)=\cases{n-1;\;{\rm if\;}G\;{\rm is\;bipartite}\\ \;\;n\;\;\;\;;\;{\rm else}}$$ So $d={n\over 2}+1$ if $G$ is bipartite and $d={n\over 2}$ else. Clearly we can extend this results to all graphs, not just connected.

But I'm unable to get an elementary solution.

Answer 1

Here is a solution that would/should be accepted in the condition of a Romanian Olympiad problem for 18yo college students. It does not use vector spaces (over a finite field), and the existence of a basis or alternaively the definition of the dimension (and the fact that dimension is well defined). But it uses some concepts related to finite groups and subgroups, mainly a result of Lagrange for finite - even abelian - groups. The proof of this result is related only to building an equivalence relation. This being said, i think the following lines can be guessed already...

---

Let $1,2,\dots,e$ build the index set $E$ of edges of the graph. We use the colors $0,1,2$ which are the elements of the field $F=\Bbb F_3=\Bbb Z/3$ with three elements. Let $G=F^E$ be the group of all tuples $a=(a(1), a(2),\dots, a(e))$ with entries in $F$, one may think equivalently of functions $a$ from the index set $E$ to the field $F$. Addition is done on components. Let $H$ be the subset (soon recognized as a subgroup) of all $a\in G$ such that for all vertices $i$ of the given graph, denoting by $\varepsilon_1,\varepsilon_2,\varepsilon_3$ the three different edges from $i$ we have in $F$ $$ a(\varepsilon_1)+a(\varepsilon_2)+a(\varepsilon_3)=0\ . $$ Elements in $H$ correspond to good colorings, since the solutions of $x+y+z=0$ for $x,y,z$ in $F$ are exactly those with either $x=y=z$ or $\{x,y,z\} =\{0,1,2\}$. One can easily check that $0=(0,0,\dots,0)$ is in $H$, that $H$ is closed w.r.t. to taking sum and difference, so $H$ is a subgroup of $G$. By Lagrange's Theorem, the cardinality of $H$ divides the cardinality of $G$ - which is $3^e$.

$\square$

Answer 2

Let $T \subset E$ be an arbitrary spanning tree on $G$, and let $r$ be an arbitrary vertex to use as the root of $T$. Let's call a coloring quasi-good if it is good except at $r$.

Claim: Given an arbitrary coloring of $E \setminus T$, there is a unique coloring of $G$ that is quasi-good.

Proof: We proceed by induction on the number of edges $T'$ of $T$ not yet colored, with the hypothesis that $T'$ is a subtree of $T$ and for any vertex $v \neq r$, if the partial coloring gives a color to each edge incident to $v$, then the three edges have either distinct or equal colors.

Suppose that $T' \neq \emptyset$, and let $v \neq r$ be a leaf of $T$, with incident edges $e_1,e_2,e_3$ where $e_1 \in T$. If $e_2$ and $e_3$ have the same color, then $e_1$ must have the same color too in any good coloring compatible with the colors given so far. If $e_2$ and $e_3$ have different colors, then $e_1$ must have the third possible color. Hence there is always exactly one way to extend the partial coloring to $e_1$ while staying (partially) good. Finally notice that $T' \setminus \{e_1\}$ is a subtree of $T'$ and $T$. By induction hypothesis we may now color $T'$ and obtain a quasi-good coloring of $G$.

---

The proof of the claim is somehow similar (but simpler) to an argument made in a beautiful proof of Brooks' theorem by Tamás Fleiner.

When $G$ is bipartite, this procedure actually gives a good coloring (that is, even $r$ is well-colored). Indeed, start from a uniform coloring (each edge has the same color), which is by definition a good coloring. Then for each edge $e \in E \setminus T$, consider $C_e$ the even cycle in $T \cup \{e\}$, and if $e$ does not have the desired color, do $+1$ on each even edge and $-1$ on each odd edge of $C_e$ (choosing the first edge such that after this operation, the color of $e$ is the same as in the partial coloring). One can easily check that modifying a good coloring by alternating along an even cycle gives a good coloring. So in the end we get a good coloring coherent with the partial coloring of $E \setminus T$. Hence the number of good colorings is the same as the number of partial colorings: $3^{|E \setminus T|} = 3^{n/2+1}$.

When $G$ is not bipartite, there must be some edge $e$ with $C_e$ odd. We call such edges odd. If $e$ is an odd edge, instead of considering $C_e$, we may consider the tripod $D_e$ that is the union of the two paths from the extremities of $e$ to $r$. Then given any quasi-good coloring and a tripod $D_e$, one can change by $+1$ or $-1$ the color of each edge on $D_e \cup \{e\}$ and obtain another quasi-good coloring (the $+1$ and $-1$ must be alternating on each path from the center of the tripod to each leaf, and the edges incident to the center must be changed by the same value).

Now let $e$ be an odd edge, and choose an arbitrary coloring of $F := E \setminus T \setminus \{e\}$. Starting from a uniform coloring and using $C_f$ or $D_f \cup \{f\}$ for any $f \in F$, one can get three quasi-good colorings coherent with our partial coloring of $F$, one for each possible color for $e$. A simple case analysis suffices to check that exactly one of these three colorings must be a good-coloring of $G$. This proves that there are as many good colorings of $G$ as the number of partial colorings of $F$, that is $3^{n/2}$.