2 votes 2 votes 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 Graph Theory graph-theory + – someshawasthi asked Mar 27, 2023 someshawasthi 501 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kabir5454 commented Mar 27, 2023 reply Follow Share 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$. 0 votes 0 votes parth023 commented Mar 27, 2023 reply Follow Share @Kabir5454 is there any formal method for such questions? 0 votes 0 votes Kabir5454 commented Mar 27, 2023 reply Follow Share You will get it automatically after practice some pyq .I don’t know any formal method .. 0 votes 0 votes Please log in or register to add a comment.