Aula 25 - Grafos - Matemática Discreta 2021 2

Aula 25 Grafos MAT13700 Matematica Discreta Ricardo Colorindo mapas Teorema das 4 cores Teorema Todo mapa planar pode ser colorido usando ate 4 cores Conjectura Guthrie em 1852 Prova com uso do computador Appen Hakken 1976 1989 Mapas e grafos Teorema das 5 cores Teorema Todo grafo planar tem um vertice de grau no maximo 5 Teorema das 5 cores Teorema Todo grafo planar pode ser colorido usando ate 5 cores Demonstracao Por inducao sobre n o numero de vertice do grafo G Suponha que todo grafo com n vertices pode ser colorido com 5 cores e que G tem um vertice v com grau menor ou igual a 5 v tem grau menor ou igual a 4 Teorema das 5 cores Teorema das 5 cores Teorema das 5 cores Teorema das 5 cores K5 Referˆencias 1 Matematica Discreta Lovasz Pelikan Vesztergombi 2 Analise Combinatoria e Probabilidade Morgado Pitombeira Carvalho e Fernandez 3 Matematica Comcreta Graham Knuth Patashnik 4 Princıpios de Combinatoria e Probabilidade Tertuliano Franco SBM 2020 5 Matematica Discreta Morgado e Carvalho PROFMAT 6 httpsenwikipediaorgwikiFourcolortheorem