Can you color this graph, such that every vertex receives some color, no two adjacent vertices receive the same color, and number colors used is minimized?
I've read about Backtracking Method, and here is my try:
Using the greedy algorithm, we start with 1 color - quickly seeing that it won't work. With 2, I was able to fill out 4 circles before seeing that the next circle I fill in will cause the one afterwards to be adjacent to the same colored ones. With 3 colors, I found the following solution (I was not able to attach an image here... so I attempted to do it with spaced letters. Hopefully my formatting stays the same when I submit the answer).
R
G Y
Y G
G
R R
If we start from the initial vertex, we can assign it a color (say blue)As we keep traversing through the graph, we assign alternate colors and check for common edge between them.The graph has 3-chromatic number. The image is shown below.