0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What have you tried? $\endgroup$
    – user113102
    Oct 29, 2019 at 16:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – EGME
    Nov 3, 2019 at 16:50
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – EGME
    Nov 3, 2019 at 16:53

You must log in to answer this question.

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