GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 29

Question

A connected graph $G$ is chromatically $k-$critical if the chromatic number of $G$ is $k$, but for every vertex of $G$, the chromatic number of the graph obtained by deleting this vertex from $G$ is $k-1$. Which of the following is/are correct? (Mark all the correct options) $(C_n$ denotes the cyclic graph on $n$ vertices and $W_n$ denotes the wheel graph on $n$ vertices)

• A. $C_{n}$ is chromatically $3-$critical whenever $n$ is an odd positive integer, $n\geq3$.
• B. $W_{n}$ is chromatically $3-$critical whenever $n$ is an odd integer, $n\geq 3$.
• C. $W_{n}$ is chromatically $4-$critical whenever $n$ is an even integer, $n\geq 4$.
• D. If $G$ is a chromatically $k-$critical graph, then the degree of every vertex of $G$ is at least $k-1$.

Answer 1

A cycle graph of odd order has
$\chi(C_{2n+1})=3$, and that of even order has $\chi(C_{2n})=2.$

So, $C_{n}$ is chromatically $3-$critical whenever $n$ is an odd positive integer, $n\geq3$ as removing any vertex removes the cycle making it a line graph which has chromatic number $2.$ So, I is TRUE.

A wheel graph of order $n+1$ is obtaining from $C_{n}$ by connecting all it's vertices
to a new vertex.  A wheel graph of odd order
has $\chi(W_{2n+1})=3$, and that of even order has $\chi(W_{2n})=4.$ Here, $W_{2n+1}$ is not $3-$ critical as removing any vertex from the cycle part won't reduce the chromatic number. But $W_{2n}$ is $4-$ critical as removing either the new vertex or any vertex from the cycle part will make the chromatic number as $3.$ So, B is FALSE and C is TRUE.

If $G$ is a chromatically $k-$critical graph, then the degree of every vertex of $G$ is at least $k-1$. Suppose to the contrary that there is a vertex $v$ with $deg(v) \leq k - 2.$ Since $G$ is critically $k-$ chromatic, then $ G - v$ is $k-1$ colorable. But since $v$ has at most $k-2$ neighbors, we can color it with one of the remaining colors, and get a $k -1$ coloring of $G$ which contradicts the fact that $G$ is $k-$chromatic. IV is TRUE.

Comments

I am commenting for option D. in this question

---

Why option B is false? ….it is satisfying for all the wheel graphs of odd vertices

---

@Deepak-Poonia sir

I am unable to decode last line please help