 # Clever proof for showing that if a graph G is critically k-colorable then &#x03B4;<!-- δ --> ( Mohamed Mooney 2022-06-26 Answered
Clever proof for showing that if a graph G is critically k-colorable then $\delta \left(G\right)\ge k-1$
While reading for my graph theory class, I came across a short - yet curious - proof for the following theorem: if a graph G is critically k−colorable then $\delta \left(G\right)\ge k-1$. Here is the proof to the claim:
Suppose (for a contradiction) that G is k-critical and that $v\in V\left(G\right)$ satisfies $\text{deg}\left(G\right). Then $G-v$ has a $\left(k-1\right)-$ coloring, and this coloring extends to a $k-1$- coloring of G. This yields a contradiction.
Everything in this proof makes sense besides one particular item: in the second line, what does the author mean by extending a coloring from a subgraph of G to the whole graph? In addition, why does $G-v$ have a $\left(k-1\right)$ coloring that extends to all of G (if that makes any sense)? I understand this may seem like an easy Google search but to be honest I can't find anything helpful and figured someone could provide some insight.
Note that this is not a homework question but simply for going beyond what I am learning in class.
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Cristian Hamilton
Step 1
In the second line, what does the author mean by extending a coloring from a subgraph of G to the whole graph?
Recall that a coloring formally is a function $f:V\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ for some integer k. So the notion of extension is basically the same as it would be for functions in other cases (extending a function from some substructure to a larger one).
In addition, why does $G-v$ have a $\left(k-1\right)$ coloring that extends to all of G (if that makes any sense)?
We have a coloring $f:V\left(G-v\right)\to \left\{1,2,\cdots ,k-1\right\}$ from k-criticality. We then define a coloring $\stackrel{~}{f}:V\left(G\right)\to \left\{1,2,\cdots ,k-1\right\}$ where $\stackrel{~}{f}=f$ on $V\left(G-v\right)$. To complete the extension, we need to define $\stackrel{~}{f}\left(v\right)$.
Step 2
Notice that ${\mathrm{deg}}_{G}\left(v\right) by hypothesis (we can choose such a v where ${\mathrm{deg}}_{G}\left(v\right)=\delta \left(v\right) in this approach by contradiction). Hence, there are at most $k-2$ nodes in V(G) adjacent to v, which does not exhaust all of the possible $k-1$ colors in $f,\stackrel{~}{f}$. Consequently, let $\stackrel{~}{f}\left(v\right)$ be any of the colors not taken up by a neighbor of v.
This ensures that $\stackrel{~}{f}$ is indeed a $k-1$ vertex-coloring. However, this contradicts the k-criticality of G, in the sense that deleting v does not change the chromatic number of G.

We have step-by-step solutions for your answer!