Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:teobruijnerdos [2022/06/22 23:01] – felipe
+++ grafos:teobruijnerdos [2022/06/22 23:49] (atual) – edição externa 127.0.0.1
@@ Linha 9: / Linha 9: @@
 ----
-//Demonstração// **(para um grafo arbitrário)**:
+//Demonstração// **(para um grafo arbitrário)**: Sejam $S := \{1, ..., k\}$ e $\mathcal F$ a coleção de todos os subconjuntos finitos de $V$. Para cada $Y \in F$, seja $\mathcal A (Y)$ o conjunto das $k$-colorações de $G[Y]$. Seja $\mathcal Y \subseteq \mathcal F$. Tomemos uma $k$-coloração do grafo finito $G[\bigcup \mathcal Y]$. Podemos encontrar uma função $V \to \{1, ..., k\}$ que induz coloração em $G[Y]$ para todo $Y \in \mathcal Y$. Pelo princípio da compacidade, induzimos uma $k$-coloração em $G$.