discrete mathematics

Question

The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal to

A    24

B    27

C    36

D    None of the above

Comments

27 ?

---

yes,looks correct to me!

---

This would be the graph .

Explanation :- Given graph is 3 colorable and to get maximum number of edges with 9 vertices we have to consider the chromatic number of graph as 3 .

Now chromatic number is 3 means we partitioned the vertex set in 3 container .Now number of vertices is 9 so we can think of the each container contain 9/3=3 vertices.

You can think of it as bipartite graph where as in bipartite graph we have two container as chromatic number is 2 but here we have 3 container as we have chromatic number is 3 .

So number of edges = $3*3+3*3+3*3=27$.

---

@Kabir5454 is there any formal method for such questions?

---

You will get it automatically after practice some pyq .I don’t know any formal method ..