# Graphs: Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color.

Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color.

My work so far:
We know that for each vertex, $v_i$, it's degree is $d(v_i)=16$, because the graph is $K_{17}$. Therefore, the number of edges is ${17\cdot16 \over 2} = 17\cdot8$.

We can divide the edges for $8$ sets (for every color).
Therefore, ${17\cdot8 \over 8} = 17$.

So, now I need to show somehow that I can arrange the edges as the question asked for.
How to do that? I think I'm missing a theorem or a principle for that cause.

• Can you clarify what you mean by a "painting" of a graph? This is not a standard graph theory term in English. – Casteels Mar 6 '14 at 9:56
• Yeah. I guessed I will be misunderstood. Painting = Coloring. – AnnieOK Mar 6 '14 at 10:03
• – AnnieOK Mar 6 '14 at 10:05
• Ok so you want a coloring of the edges with 8 colors and with the property that the edges of any given color forms a Hamiltonian cycle? Is that right? – Casteels Mar 6 '14 at 10:05
• Yes. Hamiltonian cycle would be the desired definition. – AnnieOK Mar 6 '14 at 10:06

Hint: Think about the group $(\mathbb{Z}_{17},+)$ of integers modulo the prime number $17$, and consider the sequences $(0,k,2k,3k,\ldots,16k)$ for $k=1,2,\ldots,8$.
• What does the notation $(\mathbb{Z}_{17}, +)$ means? – AnnieOK Mar 6 '14 at 12:28
• That's ok, you don't really need any group theory, just the modular arithmetic! So start by labelling your vertices by $0,1,\ldots,16$ (considered as the elements of the integers mod 17) then try to follow the hint. That 17 is prime is important here. – Casteels Mar 6 '14 at 13:05