a game of coloring edges of graph

I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the graph or how can I tell this is not possible.

• If the clique was completely white, then it is not possible. Sep 26 '13 at 15:09
• @CalvinLin Is this the only case? When we see a completely white triangle then also we can say that this is not possible.What about how to go about coloring the graph if it is possible. Sep 26 '13 at 15:12

Ket $K_n$ be the complete graph with $n\geq3$ vertices (there is nothing special with $n=5$). A black-and-white coloring of its edges is admissible if all triangles have $1$ or $3$ black edges.

When a partial edge-coloring of $K_n$ is given denote by $\Gamma$ the subgraph of $K_n$ consisting of all $n$ vertices and the colored edges.

Theorem. (i) A partial edge-coloring of $K_n$ can be extended to an admissible full coloring iff $\Gamma$ contains no bad cycle, i.e., a cycle with an odd number of white edges. (ii) When $\Gamma$ contains no bad cycle the extension can be done in $2^{b_0-1}$ ways, where $b_0$ is the number of connected components of $\Gamma$.

Proof. An admissible coloring cannot have a bad cycle: If there were such a cycle there would be a shortest one, $$\gamma:=\{v_0,v_1,v_2,\ldots,v_r,v_0\}\ .$$ Since the coloring is admissible the triangle $\{v_0,v_1,v_2,v_0\}$ is a good cycle, and it is then easy to see that $\gamma':=\{v_0,v_2,\ldots,v_r,v_0\}$ is a bad cycle shorter than $\gamma$.

This shows that the condition formulated in (i) is necessary.

To prove the sufficiency we consider the given partial black-and-white edge-coloring as $1$-cochain $f^1:\ E(\Gamma)\to{\mathbb Z}_2$, where black corresponds to $0$ and white to $1$. Let $\Gamma'=(V',E')$ be a connected component of $\Gamma$ and select a spanning tree $T$ of $\Gamma'$. Since $T$ is simply connected there exists a $0$-cochain $f^0:\ V'\to{\mathbb Z}_2$ such that for all edges $e=\{u,v\}$ of $T$ one has $$f^1(e)=f^0(u)-f^0(v)\ .\tag{1}$$ Two vertices $v_1$, $v_2$ of $\Gamma'$ get the same $f^0$-value iff walking from $v_1$ to $v_2$ along edges of $T$ one passes through an even number of white edges. This $f^0:\ V'\to{\mathbb Z}_2$ is determined up to an additive constant; so there are exactly two such $f^0$. When $e=\{u,v\}$ is an edge of $\Gamma'$ which is not in $T$ then the coboundary condition $(1)$ is automatically fulfilled for $e$; because otherwise one could at once exhibit a bad cycle in $\Gamma$.

When the above construction has been performed on each of the $b_0$ components of $\Gamma$ one can collect the chosen partial $f^0$ to a global $f^0:\ V(K_n)\to{\mathbb Z}_2$ and then finally color the remaining uncolored edges of $K_n$ such that the condition $(1)$ is fulfilled throughout. It is easy to see that the resulting edge-coloring of $K_n$ is admissible.

Given the $b_0$ choices we had when fixing the partial $f^0:\ V'\to{\mathbb Z}_2$ it follows that (ii) can be considered proven as well.

Hint: Given a (complete) coloring of the clique, each vertex of the form $v_{i} v_{i+2}$ is uniquely determined.

It then remains to check that triangles of the form $v_i , v_{i+2}, v_{i+4}$ satisfy the conditions.

Hint: Assume that such a coloring is possible. Label the black edges $-1$ and the white edges $1$. Then, we know that the product each triangle is $-1$. Use this to get conditions on the edges.

• what do you mean when you say "each vertex of the form vivi+2 is uniquely determined" Sep 26 '13 at 15:28
• Can you please explain your method ( the first hint ). Sep 26 '13 at 19:11
• @user2179293 If $v_i v_{i+1}$ is black and $v_{i+1} v_{i+2}$ is white, what must be the color of $v_i v_{i+2}$? Do this for the different combinations of black and white. Sep 26 '13 at 20:20