I need this proof:
Let $G$ be a graph such that $\chi (H) <\chi (G)$ for every subgraph $H$ of $G$. A graph is called $k$-critical, if in addition $\chi (G) = k$. Prove that $\chi (G) ≤ \delta + 1$.
3 of 3
Removed deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info
Martin Sleziak
- 4.7k
- 4
- 35
- 40
Graph Coloring Proof χ (G) ≤ δ + 1 for k-criticals
dantopa
- 7
- 2