# DM-Graphs-Q6

A graph is critical if the removal of any one of its vertices (and the edges adjacent to that vertex) results in a graph with a lower chromatic number.

Which of the following graph is critical?

$\text{I. }K_n$

$\text{II. }C_n$

$(A). \text{ Only I}$

$(B). \text{ Only II}$

$(C). \text{ Both I and II}$

$(D). \text{ Neither I or II}$

reshown Jul 13

+1 vote
if a graph is complete then is n- colorable if its K(n)   therefore if we remove 1 vertex it becomes K(n-1) hence it becomes n-1 colourable

here K(n) represents a complete graph with n vertices,

therefore statement 1 is true

Now lets take a C(n) i.e a cyclic graph of n-vertices, say C(4) and since it has even vertices, therefore, its 2-colourable but if we remove 1 vertex it remains 2-colourable only...but in case of odd cyclic graph like C(3) or C(5) it would have been critical but since its not mentioned, therefore we consider both cases and hence statement 2 is false

therefore A
answered Jul 13 by (1,120 points)