How to do such questions.

Question

If $G$ is a bipartite graph with 6 vertices and 9 edges, then the chromatic number of $\overline G$ =

Comments

should be 3

---

Yes ans is 3.

Try constructing bipartite graph first, by dividing vertices into 2 groups. Here it is very easy 3 vertices on one side and 3 on other side. And all possible edges (9 edges) are connected.

Take complement of it. Find chromatic number.

Anybody got any shortcut?

---

max   no of edge in Bipartite graph=(n^2)/4 , when n is equally distributed both side.

here n=6, max edge =9 both side n/2  vertices means 3.

so G' will be disconnected having two component with 3 vertices each make odd cycle with 3-3 edges.

so chromatic no 3.