Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
