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

1 Answer 1

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$
2
  • $\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, 2014 at 15:43
  • $\begingroup$ and 1! If you allow $K_1$ that is. $\endgroup$
    – user21820
    Jan 17, 2014 at 16:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .