# Find how many colors are needed to color all vertices

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. 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 :)

• 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.) – anon_user Mar 30 '20 at 5:03
• What did you use to build that diagram? :O – m4n0 Mar 30 '20 at 5:12
• @ManojKumar Paint :P – Swati Mar 30 '20 at 5:13
• @Hugh Sorry, i was not knowing that this question is already present somewhere :) – Swati Mar 30 '20 at 5:14

## 1 Answer

Four colors are needed.

Example coloring using a greedy algorithm: 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) • well explain :) – Swati Mar 30 '20 at 8:49