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.
On
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.
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.