17
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Very nice linear algebra solution! $\endgroup$ Jan 1, 2022 at 13:31
  • $\begingroup$ Happy new year to you too! You might be interested in reading the various types of solutions to this problem here. $\endgroup$ Jan 1, 2022 at 13:34
  • 2
    $\begingroup$ You could try "unpacking" the linear algebra to see if it's hiding a more elementary proof. That is, instead of just applying a theorem from linear algebra, carry out the proof of that theorem directly on this case (and potentially simplify it in the process). $\endgroup$
    – Karl
    Jan 1, 2022 at 21:12
  • 1
    $\begingroup$ I am of the thought too that your linear-algebraic solution, is the solution. I mean, how would you prove that an $n$-dimensional hypercube has exactly $2^n$ vertices? Is the proof of this combinatoric or linear-algebraic? Maybe it is both at the same time? $\endgroup$
    – Mike
    Jan 2, 2022 at 16:55
  • $\begingroup$ This would be a very nice Olympiad problem. By distraction (this hard job), my first perception was the "cousin" problem, where we are coloring vertices, not edges. The cousin condition for a "good" coloring being that of having always for each vertex three adjacent vertices with either same color or (three) different colors. I think, the one or the other framework would lead to interesting problems (at least from the didactical point of view) for Olympiads. (Even simple versions, as getting the number of good colorings for the cube or Petersen graph, are good "exercises".) Plus one! $\endgroup$
    – dan_fulea
    Jan 6, 2022 at 16:14

2 Answers 2

7
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Very very nice. $\endgroup$
    – nonuser
    Jan 6, 2022 at 18:55
2
+200
$\begingroup$

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}$.

$\endgroup$
7
  • $\begingroup$ For the first paragraph, leaf is in $T$ not $E\setminus T$? And you are doing induction on what? $\endgroup$
    – nonuser
    Jan 3, 2022 at 21:58
  • $\begingroup$ What is uniforming coloring? $\endgroup$
    – nonuser
    Jan 3, 2022 at 22:02
  • 1
    $\begingroup$ $T$ is the tree, so yes, a leaf of $T$. The induction is on the number of edges not yet colored. A uniform coloring is a constant coloring, all the edges have the same color. Uniform colorings are good by definition. $\endgroup$
    – Guyslain
    Jan 4, 2022 at 6:53
  • $\begingroup$ How does the induction step works? Can you write down this claim as whole statement. I mean your induction works for all graphs or just 3-regular...? $\endgroup$
    – nonuser
    Jan 4, 2022 at 8:01
  • $\begingroup$ Yes it only works for 3-regular graphs. We need that any choice of colors on $d-1$ of the $d$ incident edges of a vertex constrains the choice to a unique color for the last incident edge. This happens to be the case for good coloring of 3-regular graphs. $\endgroup$
    – Guyslain
    Jan 4, 2022 at 8:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .