2
$\begingroup$

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$ enter image description here

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot! I truly enjoyed going through your solution! I assumed that $17$ would be a fit too and i was going in a direction where i would find a relation with $2^k + 1$ but that way i would not get all the solutions. So basically the solutions are $5, 9, 13, 17, 21..$ $\endgroup$ – newGuy Jan 17 '14 at 15:43
  • $\begingroup$ and 1! If you allow $K_1$ that is. $\endgroup$ – user21820 Jan 17 '14 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.