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.

  • 1
    $\begingroup$ Can you clarify what you mean by a "painting" of a graph? This is not a standard graph theory term in English. $\endgroup$ – Casteels Mar 6 '14 at 9:56
  • $\begingroup$ Yeah. I guessed I will be misunderstood. Painting = Coloring. $\endgroup$ – AnnieOK Mar 6 '14 at 10:03
  • $\begingroup$ Here. en.wikipedia.org/wiki/Edge_coloring $\endgroup$ – AnnieOK Mar 6 '14 at 10:05
  • $\begingroup$ 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? $\endgroup$ – Casteels Mar 6 '14 at 10:05
  • $\begingroup$ Yes. Hamiltonian cycle would be the desired definition. $\endgroup$ – 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$.

  • $\begingroup$ What does the notation $(\mathbb{Z}_{17}, +)$ means? $\endgroup$ – AnnieOK Mar 6 '14 at 12:28
  • $\begingroup$ Integers mod 17 as a group under addition. Have you learned about these things yet? $\endgroup$ – Casteels Mar 6 '14 at 12:46
  • $\begingroup$ I am familiar with modular arithmetic, but not with group theory. $\endgroup$ – AnnieOK Mar 6 '14 at 12:50
  • $\begingroup$ 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. $\endgroup$ – Casteels Mar 6 '14 at 13:05

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.