7.5

Graphs with max degree 2, can be bipartite (even number of edges) or tripartite (odd number of edges)

---

Consider a triangle (3 edges, 3 vertices): it's not bipartite even though every node has an even number of edges and the graph has an even number of edges.

---

For such a graph, such that the degree of every vertex is at most 2, we can use a DFS traversal, coloring the child the opposite color of the parent. When we see a Back edge, we color the currently discovered child with a color different that the parent, and also different from the ancestor discovered through that back edge.

Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)

---

Another Solution:

A graph whose each vertex has degree at most K has chromatic number less than equal to K + 1.

It is given that each degree has vertex at most 2, therefore determine whether the graph is two colourable or not with the help of BFS traversal. If it is then the answer is 2 otherwise the answer is 3. If graph has only one vertex then the answer will be 1.

Let me know whether the solution is right? (sah.sslpu@gmail.com) BTW it is right!

Back to Chapter 7