Mohamed Mooney

## Answered question

2022-06-26

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.

### Answer & Explanation

Cristian Hamilton

Beginner2022-06-27Added 23 answers

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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?