Coloring of $K_n$ with red and blue st. each vertex is incident with $\frac{n-1}{2}$ blue edges

Question

Let $n=1$ (mod 4). Prove that there is a coloring of the edges of $K_n$ with two colors (say red and blue) such that each vertex is incident with exactly $\frac{n-1}{2}$ blue edges.

I know that I need some smart strategy for construction of particular coloring for every $n$, but I cannot figure it out. Does anybody have an idea?

Answer 1

Adding some details to @Qise's answer. For $n=5$, note that $K_5$ is a pentagon with a star inside. Simply colour the $5$ edges of the pentagon blue and the $5$ edges of the star red (or vice-versa), and you have it.

Suppose for $n=4k+1$ you have such an edge colouring of $K_n$. Note that the blue degree of each vertex is $2k$. Divide the $4k+1$ vertices into four sets of $k$ vertices each, say $V_1, V_2, V_3, V_4$ and a single vertex, $v$.

Now for $n'=4k+5$ you add four vertices - say $u_1, u_2, u_3, u_4$. Colour all the edges between $u_1, u_2$ and $V_1, V_2$ blue, and between $u_1, u_2$ and $V_3, V_4$ red. Similarly, colour all the edges between $u_3, u_4$ and $V_3, V_4$ blue and those between $u_3, u_4$ and $V_1, V_2$ red.

Now note that the vertices in $V_1,...,V_4$ have achieved blue degree $2k+2$, as required. The only edges left to colour in $K_{n'}$ are the edges of the $K_5$ induced by $u_1,..., u_4, v$. Use the colouring of $K_5$ in step 1, following which the blue degree of each of these is now $2k + 2$, as required.

Answer 2

By induction:

1. initial step is to find a coloring for $K_5$. (Edit: actually you can start from $K_1$ and the induction step tells you how to build a proper coloring for $K_5$ but maybe it's less intuitive.)
2. Let $n = 4k +1$. By IH we have a coloring $c$ on $V$ such that $d_b(v) = 2k \; \forall v$. Now let's add four additional vertices $a, b, c$ and $d$. We need to find the color the edges incident to these, so $d'_b(v) = 2k +2 \; \forall v$; so increasing by 2 for the original vertices and $2k+2$ edges for the new ones. Let $A, B, C, D, \{s\}$ a partition of our $4k+1$ initial vertices into four sets of identical size $k$ and a vertex alone. Color in blue the edges in the picture:

Answer 3

Arrange the $n=4k+1$ vertices in a circle and let each vertex be joined by red edges to the $k$ nearest vertices on either side, and by blue edges to the remaining $2k$ vertices.

More generally, a $k$-regular simple graph on $n$ vertices can be constructed whenever $0\le k\le n-1$ and $nk\equiv0\pmod2$.