# A problem about edge bicolored complete graphs 2

Let $$K_n$$ be the complete graph on $$n$$ vertices, $$n>3$$, and let $$C$$ be an edge 2-coloring of $$K_n$$ with edge colors red and blue. Let a 4-circuit with exactly three red edges or exactly three blue edges be called a mostly monochromatic circuit (mostly red, and mostly blue). Let M be the number of mostly monochromatic 4-circuits in $$K_n$$. Our problem is the following:

Problem Show that if we switch the color of an edge in the complete graph, the change in M is even.

• What have you tried? Oct 29, 2019 at 16:38

We can count the amount of 4 circuits involving an edge $$xy$$ by picking each edge in the graph not involving x or y, each of these edges creates two circuits with $$xy$$ ($$xyln$$ and $$xynl$$). that number equals $$(n-2) * (n-3)$$ and is always even. note that each of the circuits involving $$xy$$ changes its state when altering $$xy$$'s color, as in if it was mostly monochromatic, it stops being so, and if it wasn't then it becomes one. so we are changing the state of an even number of circuits.

• This is a very nice idea ... it seems to lead to the proof of a generalized version of the problem ... more about that perhaps in another post.
– EGME
Nov 3, 2019 at 16:50

We shall prove the following stronger result.

Let $$S$$ be a set of vertices of $$K_n$$. Let $$M(S,n)$$ be the number of mostly monochromatic 4-cycles in $$K_n$$ which have to include the vertices of $$S$$. Then $$M(S,n)$$ is even.

Proof

Consider a counterexample with $$n-|S|$$ minimal.

First suppose that there is a vertex $$v$$ of the complete graph which is not in $$S$$. A mostly monochromatic 4-circuit in $$K_n$$ which includes the vertices of $$S$$ either includes $$v$$ as well or does not include $$v$$. Therefore $$M(S,n)=M(S\cup \{v\},n)+M(S,n-1).$$ By minimality, both terms on the RHS are even and so $$M(S,n)$$ is even after all.

We can therefore suppose that $$S$$ contains all the vertices of $$K_n$$. If $$|S|>4$$ or $$n<4$$ then $$M(S,n)=0$$ is even. So we can suppose $$|S|=n=4$$ and it is easy to check the few possibilities for this.

• Right ... in more general versions of the problem you would end up checking the possibilities for n=6, n=8, etc. While this is not immediate, and not feasible for large n, it seems that it would be true upon extending an idea in answer 1 above ... see my comment to that answer ... I hope to post the problem in full generality later, although it now seems to be solved, so I would need to have a good excuse to post it ... when I posted these questions, the problem was not know to be solved
– EGME
Nov 3, 2019 at 16:53