A simple problem about edge bicolored complete graphs

Question

Let $K_n$ be the complete graph on $n$ vertices, where $n$ is even and greater than 2. Let $G$ be a spanning subgraph of $K_n$, and let $G'$ be its complement in $K_n$. The edges of $G$ and $G'$ can be thought of as two color classes in an edge 2-coloring of $K_n$.

We are looking for the simplest proof of the following (the book proof if you will):

Fact The parity of the number of paths of length 2 in $G$ and in $G'$ is the same.

Here, we are (somewhat unconventially) identifying every path $abc$ of length 2 with its "mirror version" $cba$.

We are also looking for the following

Problem Provide a procedure (maybe to generate all the paths with exactly one edge in $G$ and one edge in $G'$), so that it is evident that the number of paths with exactly one edge in $G$ and exactly one in $G'$ is even. It might be that the procedure just pairs up paths uniquely.

This is a good question here, as the gist of it is to obtain mathematical information via the procedure as in so many parity arguments. The computational aspect in itself is not so important, other than that it give the parity of the number of paths easily.

Answer 1

I think the conventional definition of path means that $v_1v_2v_3$ and $v_3v_2v_1$ are counted as two paths. In that case the result would be obvious so I shall suppose they are counted as the same path.

Proof of the Fact

Let the edges of $K_n$ be coloured either red or yellow and consider any red edge , $e$.

Let $e$ be connected on one side to $a$ red edges and therefore $n-2-a$ yellow edges. Let it be connected on the other side to $b$ red edges and therefore $n-2-b$ yellow edges. Changing the colour of $e$ to yellow reduces the number of red paths of length 2 by $a+b$ and increases the number of yellow paths by $2n-4-a-b$. We note that these numbers have the same parity.

The procedure can be repeated until there are no red edges. In that case the number of yellow paths of length 2 is $\frac{n(n-1)(n-2)}{2}$. This number is even (in fact divisible by 4) and so the parity of the number of paths of length 2 in $G$ and in $G'$ was the same throughout.

The procedure for the problem

We apply the same procedure as above. The change of colour reduces the number of paths with exactly one edge in $G$ and exactly one in $G'$ by $2n-4-2a-2b$, an even number. Continuing the procedure leads to the situation where there are no such paths and so the number was originally even.

Answer 2

Let $n$ be any positive integer. Let $G$ be any graph on $n$ vertices, and let $G'$ be its complement. Let $S$ be the number of (undirected) paths of length $2$ in $G$, and let $S'$ be the number of such paths in $G'$.

Fact. $S\equiv S'\pmod2$ if and only if $n\not\equiv3\pmod4$.

Proof. Let $d_1,\dots,d_n$ be the degree sequence of $G$ and $d'_1,\dots,d'_n$ the degree sequence of $G'$, so that $d'_i=n-1-d_i$. Observe that $$S=\sum_{i=1}^n\binom{d_i}2$$ since, for a vertex $v$ of degree $d$, there are $\binom d2$ paths of length $2$ centered at $v$. Thus $$S-S'=\sum_{i=1}^n\left[\binom{d_i}2-\binom{n-1-d_i}2\right].$$ The rest is just arithmetic. Recall that $\binom d2$ is even if and only if $d\equiv0,1\pmod4$.

Case I. $n\equiv0\pmod4$.

In this case it is easy to see that $\binom d2$ and $\binom{n-1-d}2$ always have opposite parity, so that $$S-S'\equiv\sum_{i=1}^n1\equiv n\equiv0\pmod2.$$

Case II. $n\equiv1\pmod4$.

In this case $\binom d2$ and $\binom{n-1-d}2$ have the same parity if and only if $d$ is even, i.e., $\binom d2-\binom{n-1-d}2$ has the same parity as $d$, so that $$S-S'\equiv\sum_{i=1}^nd_i\equiv0\pmod2.$$

Case III. $n\equiv2\pmod4$.

In this case $\binom d2$ and $\binom{n-1-d}2$ always have the same parity, so that $$S-S'\equiv\sum_{i=1}^n0\equiv0\pmod2.$$

Case IV. $n\equiv3\pmod4$.

In this case $\binom d2$ and $\binom{n-1-d}2$ have the same parity if and only if $d$ is odd, i.e., $\binom d2-\binom{n-1-d}2$ has the same parity as $d+1$, so that $$S-S'\equiv\sum_{i=1}^n(d_i+1)\equiv n\equiv1\pmod2.$$

Alternative proof without all those cases. As before we use the identity $$S-S'=\sum_{i=1}^n\left[\binom{d_i}2-\binom{n-1-d_i}2\right].\tag1$$ Substituting $x=d$ and $y=n-1-d$ in the identity $$\binom{x+y}2=\binom x2+\binom y2+xy\tag2$$ we have $$\binom{n-1}2=\binom d2+\binom{n-1-d}2+d(n-1)-d^2\tag3$$ whence $$\binom d2-\binom{n-1-d}2\equiv\binom{n-1}2+d(n-1)+d^2\pmod2\tag4$$ and $$S-S'\equiv\sum_{i=1}^n\left[\binom{d_i}2-\binom{n-1-d_i}2\right]\equiv n\binom{n-1}2+(n-1)\sum_{i=1}^nd_i+\sum_{i=1}^nd_i^2\pmod2.\tag5$$ Since $\sum_{i=1}^nd_i\equiv0\pmod2$ and $\sum_{i=1}^nd_i^2\equiv\left(\sum_{i=1}^nd_i\right)^2\equiv0\pmod2$, it follows that $$S-S'\equiv n\binom{n-1}2\equiv\frac{n(n-1)(n-2)}2\pmod2.\tag6$$ From $(6)$ it is clear that $$S-S'\equiv0\pmod2\iff n\not\equiv3\pmod4.\tag7$$