6
$\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 :)

Improve this question
$\endgroup$
4
  • $\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$
    – user46002
    Commented Mar 30, 2020 at 5:03
  • 1
    $\begingroup$ What did you use to build that diagram? :O $\endgroup$
    – m4n0
    Commented Mar 30, 2020 at 5:12
  • $\begingroup$ @ManojKumar Paint :P $\endgroup$
    – Swati
    Commented Mar 30, 2020 at 5:13
  • $\begingroup$ @Hugh Sorry, i was not knowing that this question is already present somewhere :) $\endgroup$
    – Swati
    Commented Mar 30, 2020 at 5:14

1 Answer 1

Reset to default
12
$\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
  • 1
    $\begingroup$ well explain :) $\endgroup$
    – Swati
    Commented Mar 30, 2020 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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