===== Uma $k$-coloração e seus subgrafos =====

A proposição na seção [[.alggul | anteiror]] mostra que todo grafo $k$-cromático possui um subgrafo de grau mínimo pelo menos $k-1$. De fato, ele possui um subgrafo $k$-cromático tal:

<WRAP round box 70%>
=== Lema ===
//Todo grafo $G$ k-cromático possui um subgrafo k-cromatico de grau mínimo pela menos $k-1$.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Dado um grafo $G$ com $\chi(G) = k$,tomemos $H \subset G$ minimal tal que $\chi(H)=k$. Se $H$ possui vértice $v$ tal que $d_H(v) \leq k-2$, podemos estender uma $(k-1)$-coloração de $H-v$ para uma de $H$, contradizendo a escolha de $H$.

<wrap right>$\square$</wrap>
</WRAP>

----

<WRAP round info 100%>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 123. Acesso em 12/06/2023.

</WRAP>