Color this graph (n=10, m=15)

Question

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?

Answer 1

I've read about Backtracking Method, and here is my try: 

Comments

I like the answer.  So, you can basically color this graph using 4 colors?  (Green, Blue, Purple, Yellow)?

---

I think I can color this graph with 3 colors only if I changed the Yellow to Purple. I just realized that it works also :)

---

OK, if you can change the yellow to purple and resubmit, I can accept the answer.

---

I just submitted the updated Graph.

---

Now my question is: How do you attach images to these answers???

:)

---

By clicking on the "attach image" button. :-)

---

Yes, I clicked on "attach image" as Prof. Amrinder said, but first I uploaded the image here https://imgsafe.org/ , then copied the link. I am not sure if there is a simple way to do it through this blog directly?

---

Thank you! Yes, it seems like 'Attach Image' doesn't attach images directly from our local machine? I tried adding the URL to my local machine with it not doing anything. Thank you Amal for suggesting imgsafe!

If someone knows the steps to do it directly from our PC, please do let us know.

Answer 2

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

                 G                 Y

Answer 3

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.