+2 votes

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}

asked Jul 12 in Discrete Maths by gbeditor (4,440 points)
reshown Jul 13 by gbeditor

1 Answer

+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 tssoumambanerjee-nit (500 points)