Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:numerdecores [2023/05/10 12:39] – piva | grafos:numerdecores [2023/06/12 14:13] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 17: | Linha 17: | ||
| - | Dem 1: | + | <WRAP round box 100%> |
| + | // | ||
| Seja $\mathcal{c}$ uma coloração de vértice de $G$ com $k=\chi(G)$ cores. Então $G$ tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes. | Seja $\mathcal{c}$ uma coloração de vértice de $G$ com $k=\chi(G)$ cores. Então $G$ tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes. | ||
| Linha 35: | Linha 36: | ||
| <wrap right> | <wrap right> | ||
| - | + | </ | |
| - | + | ||
| - | + | ||
| - | ---- | + | |
| - | Dem 2: | + | |
| - | + | ||
| - | Assim, $m \geq \frac{1}{2} k(k-1)$. Resolvendo esta desigualdade para $k$, obtemos a afirmação reivindicada. | + | |
| ---- | ---- | ||
| + | <WRAP round info 100%> | ||
| + | === Referências === | ||
| + | * Reinhard Diestel. [[https:// | ||
| + | </ | ||