# Every $k$-critical graph has a $k-1$-critical subgraph

I want to prove that any given $$k$$ ($$k \geq 2$$) critical graph $$G$$ has a $$(k-1)$$ critical subgraph. A graph is critical if any subgraph $$H \subset G$$ accepts a $$k-1$$ coloring, or in other terms, it has a chromatic number less than $$k$$.

I tried doing it by contradiction, assuming that a graph $$G$$ is $$k$$ critical but has no $$k-1$$ critical subgraphs. That is, any subgraph accepts a $$k-2$$ coloring, but $$G$$ has $$\chi(G) = k$$. I don't know where to go from here. I also thought of doing it by induction on $$k$$, since for $$k = 2,3$$, it is obvious. Then I assume I have my property for $$k$$, now I want to see what happens in $$k+1$$, but I don't know how to use my hypothesis.

Any help would be appreciated.

• You will note. If any subgraph of a graph $G$ admits a properly coloring in $k-2>0$ colors, then $\chi(G)\leq k-1$. Commented Nov 13, 2023 at 6:34

You know that removing an edge from a graph does not lower the chromatic number by more than $$1$$; and removing an isolated vertex (assuming the graph had more than one vertex to start with!) does not change the chromatic number at all.

You can assume $$k\ge3$$ since the case $$k=2$$ is obvious. Your graph $$G$$ is $$k$$-critical, so in particular it's not $$(k-2)$$-colorable.

If you can remove some edge without making the graph $$(k-2)$$-colorable, pick such an edge and remove it. Repeat this step until you can no longer remove an edge without making the graph $$(k-2)$$-colorable.

Finally, if there are any isolated vertices, remove them. You can show that the graph you're left with is $$(k-1)$$-critical.

• I see. So I then end up with a graph that can't be $k$ colorable, but by construction is not $k-2$ colorable (can I assume it is not $k-3$,$k-4$, etc colorable?). So it has to be $k-1$ colorable, in particular $k-1$ chromatic, and then use the theorem that states that any $k$ chromatic graph has a $k$ critical subgraph? Commented Nov 13, 2023 at 22:22
• Huh? Once you've got a graph which is not $(k-2)$-colorable, but you can't remove any edge (or vertex) without making it $(k-2)$-colorable, then the graph is already $(k-1)$-critical, so you don't have to use any theorem.
– bof
Commented Nov 14, 2023 at 1:58
• Oh, I see. Guess I was just overengineering the solution. Thanks for the clarification. Commented Nov 15, 2023 at 4:36