Edge Coloring a Complete Graph.

Question

The problem is: Find all natural numbers $n$ for which edges of a complete graph $K_n$ can be colored red and blue so that each vertex of a complete graph has an equal number of red and blue edges?

So I have already solved 4-5 problems with complete graphs and I am familiar with them. Complete graph with $n$ vertices has $m = n(n-1)/2$ edges and the degree of each vertex is $n-1$.

Because each vertex has an equal number of red and blue edges that means that $n-1$ is an even number $ \implies n$ has to be an odd number. Now possible solutions are $1, 3, 5, 7, 9, 11 ..$

What i did next is basically i drew complete graphs for some of these cases to see what happens. I found out that $5, 9$ are solutions but I don't know whether there is a formula or a way to determine all these numbers? Obviously i can't draw them all.

Example for $K_5$

Answer 1

Note that $K-1$ is also (trivially) a solution.

Necessry condition: If among the $n\choose 2$ edges of such a $K_n$ there are $r$ red and $b$ blue edges, we have $2r$ red edge-vertex incidences and $2b$ blue edge-vertex incidences. Also, both incidence counts must equal $n\cdot \frac{n-1}2$ as there are $\frac{n-1}2$ of them per vertex. In other words, $n(n-1)$ is a multiple of $4$, and since $n$ is odd, $n-1$ is a multiple of $4$.

Sufficient condition: Assume you have a suitable colouring of $K_n$ where $n=4m+1$ (with vertices $P_1,\ldots,P_n$). Add four new vertices $A,B,C,D$ to create a $K_{n+1}$. Colour the additional edges as follows:

1. $P_iA$ with $1\le i\le 2m$: blue
2. $P_iB$ with $1\le i\le 2m$: red
3. $P_iC$ with $1\le i\le 2m$: red
4. $P_iD$ with $1\le i\le 2m$: blue
5. $P_iA$ with $2m< i\le n$: red
6. $P_iB$ with $2m< i\le n$: blue
7. $P_iC$ with $2m< i\le n$: blue
8. $P_iD$ with $2m< i\le n$: red
9. $AB$, $BC$, $CD$: red
10. $AC$, $AD$, $BD$: blue

Note that $P_i$ with $1\le i\le 2m$ gets two additional red edges (from 2. and 3.) and two addtional blue edges (form 1. and 4.), similarly for $P_i$ with $2m<i\le n$ from 5.-8.; $A$ gets $2m+2$ blue edges (from 1. and 10.) and $2m+2$ red edges (from 5. and 9.); similarly for $B,C,D$. Thus given a suitable colouring for $K_n$ we obtain one for $K_{n+4}$. Starting with the trivial colouring of $K1$ we thus obtain suitable colourings for all $n\equiv 1\pmod 4$.