5
$\begingroup$

In this puzzle you need to identify the minimum number of colors needed to color vertices such that no two adjacent vertices have the same color.

enter image description here

Here, grey dots indicate vertices :P (sorry for bad drawing). You can use any colors to solve this puzzle. Also, you can take any vertex as the starting vertex.

All the best :)

$\endgroup$
  • $\begingroup$ I suspect that this is a duplicate question, or at least "similar enough" to an existing question. For your sake though, my answer would be three or four, as the schlegel diagram of a dodecahedron can be coloured with three (see left image here—it's slightly different—you only need to change two vertices to a fourth colour to make it work.) $\endgroup$ – Hugh Mar 30 at 5:03
  • 1
    $\begingroup$ What did you use to build that diagram? :O $\endgroup$ – m4n0 Mar 30 at 5:12
  • $\begingroup$ @ManojKumar Paint :P $\endgroup$ – Swati Mar 30 at 5:13
  • $\begingroup$ @Hugh Sorry, i was not knowing that this question is already present somewhere :) $\endgroup$ – Swati Mar 30 at 5:14
13
$\begingroup$

Four colors are needed.

Example coloring using a greedy algorithm:

enter image description here

It cannot be done with 3 since the Moser Spindle is a subgraph of this graph and it has a chromatic number of 4 (it has a minimum of 4 colors to color the vertices)

enter image description here

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ well explain :) $\endgroup$ – Swati Mar 30 at 8:49

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.