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

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?

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.

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:

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$$.