Having trouble understanding this statement: If G is k-critical, then the minimum degree of its vertices is k-1

Question

I want to prove that if a graph $G$ is $k$-critical, then $deg(v) \ge k-1,$ $ \forall v \in V_G$ , but I have no idea where to begin

A $k-$critical graph is a graph such that the chromatic number of $G$ is $k$ and for any edge in the graph, $G \backslash e$ has a proper colouring of $k-1$ colours

Answer 1

As seen in Bondy and Murty book:

By contradiction:

• Let $G$ be a $k$-critical graph with $\delta \lt k-1$
• Let v be a vertex with degree $\delta$.
• Since $G$ is $k$-critical , $G-v$ is $(k-1)$ colorable.
• Let $(V_1,V_2,.....V_{k-1})$ be a coloring of $G-v$.
• By definition v is adjacent to $\delta \lt k-1$ vértices.
• Then, there is a $V_j$ partition that doesn't contain any vertex adjacent to v. (This is because there is $k-1$ partitions and $\delta \lt k-1$.)
• So we have that :

$V_1,V_2,.. , ( V_j \cup {v} ) ,...V_{k-1}$ is a $(k-1)$ coloring of $G$ which is a contradiction.