0 votes 0 votes Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30) A 13 B 17 C n(n−1)2−13×17 D n(n−1)2−2 Graph Theory graph-theory bipartite-graph testbook-test-series + – Sahil_Lather asked Jan 27, 2023 retagged Jan 27, 2023 by makhdoom ghaya Sahil_Lather 487 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Chandrabhan Vishwa 1 commented Jan 27, 2023 i edited by Chandrabhan Vishwa 1 Jan 27, 2023 reply Follow Share G’ have two connected component of two complete graph with vertices 13 and 17 hence minimum colored required to color the graph is 17 if a complete Bipartite graph (Kn) then its chromatic number is N 1 votes 1 votes ankitgupta.1729 commented Jan 27, 2023 reply Follow Share $G_n$ is a complete bipartite graph which is having $13\times 17$ edges and So, $\overline{G_n}$ would have $2$ components each is having a complete graph i.e. $K_{13}$ and $K_{17}$ and you can verify that total edges of $K_{13}$ and $K_{17}$ is $\frac{13 \times 12}{2} + \frac{17 \times 16}{2} = 214$ which matches with the number of edges in $\overline{G_n}$ i.e. $\frac{30 \times 29}{2} \ – \ 13 \times 17 = 214.$ Now, since $K_{17}$ is complete graph, so it is having chromatic number as $17$ and $K_{13}$ is also a complete graph, so it is having chromatic number as $13.$ Now, for $K_{13}$, you can make any subset of colors from the set of $17$ colors which you are using for $K_{17}.$ Hence, you need minimum $17$ colors to properly color the graph $\overline{G_n}.$ 3 votes 3 votes Sahil_Lather commented Jan 27, 2023 reply Follow Share So it’s become basically the question of cromatic number for Kn graph. 0 votes 0 votes Please log in or register to add a comment.