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$.
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$.
Let $n= \chi(G)$ and suppose there is $v\in V(G)$ such that $d(v) < \chi(G)-1$. Then you can color $G\setminus \{v\}$ with $n-1$ colors (because of criticalness). Since $v$ has less than $n-1$ neighbors, those neighbors use up less than $n-1$ colors; let $k\in \{1,\ldots,n-1\}$ be the color that is not used. Then color $v$ with color $k$ and you colored $G$ with $n-1$ colors, contradicting that $n=\chi(G)$.