Indução e eu não somos amigos. Mas eu tentei resolver este exercisio...
Eu ainda tenho problemas argumentando questões por indução... Alguem pode-me
dizer se meu intento está certo ou errado, e dar dicas?
Aqui va:
Indução em n (número de vértices do grafo)
Obs 1: (Como não temos Nu mayuscula em LaTeX, denoto \(\nu\) a vizinhança de
um vértice)
Obs 2: (\(\chi\) denota o número cromático)
_Base da indução: _ \(n - 1\)
\(\chi(G) \leq \delta(G) + 1 \Rightarrow X(G) \leq \Delta(G) + 1\)
Hip. Indução \(\forall G, \chi(G) \leq \Delta(G) + 1\)
Paso Suponha: \(|V(G)| = k - 1, k < n\)
Seja \(G\) um grafo com \(k - 1\) vértices, com o grau máximo \(\delta(G)\). Dado
um vértice \(v \in V(G)\) com \(d(v) = \Delta(G)\), vai precisar de \(\Delta(G)\)
cores para colorear \(\nu(v)\). Além, o vértice \(v\) precisa ter um cor diferente.
Isso da garantía que \(\chi(G) = \Delta(G) + 1\). Caso \(d(v) < \Delta(G)\), \(\nu(G)\)
vai precisar de menos cores que \(\Delta(G)+1\) para colorear \(\nu(v)\).
Com isso se prove que \(\Delta(G) = k - 1 \Rightarrow \chi(G) \leq \Delta(G)
+ 1\)
Enchergando mais um vértice...
_(Hip Indução) _ \(\Rightarrow \Delta(G) = k \Rightarrow \chi(G) \leq \Delta(G)
+ 1\)
Tem dois casos:
_Caso 1: _
O vértice enchergado não pertence a \(\nu(v) \Rightarrow \) A quantidade de
cores não vai mudar, garantindo ainda que \(\chi(G) \leq \Delta(G)+1\)
_Caso 2: _
O vértice enchergado pertence a \(\nu(v)\). O grafo vai prcisar mais de um cor
para coloear o grafo. Mas \(\Delta(G)\) vai-se incrementar em 1, ainda cumprindo
o fato de que \(\chi(G) \leq \Delta(G)+1\)
O que é chi(G)?
Usualmente é o número cromático.
É isso. \(\chi(G)\) é o número cromático.
http://www.educ.fc.ul.pt/icm/icm2001/icm33/numerocromatico.htm