Aula 24 - Grafos - Matemática Discreta 2021 2

Aula 24 Grafos MAT13700 Matematica Discreta Ricardo Colorindo grafos Teorema Um grafo e colorıvel com 2 cores se e somente se ele nao contem um ciclo ımpar Supongamos que de nos toman como impares Colorindo grafos Dizemos que um grafo e kcolorıvel se podemos colorir os vertices com k cores diferentes sem que dois vertices adjacentes tenham a mesma cor mas nao podemos colorir com k 1 cores Neste caso dizemos que o numero cromatico do grafo e k Colorindo grafos Teorema Se todo vertice de um grafo tem grau menor ou igual a d entao podemos colorir o grafo com d 1 cores Demonstracao Por inducao sobre o numero de vertices n Se o numero de vertices do grafo e menor ou igual a d 1 podemos colorir o grafo com d 1 cores G V A Colorindo mapas 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 mapa planar pode ser colorido usando ate 5 cores Proposicao Um grafo planar com n vertices tem no maximo 3n 6 arestas Demonstracao V F A 2 Teorema das 5 cores Teorema das 5 cores Teorema Todo grafo planar tem um vertice de grau no maximo 5 Demonstracao Teorema das 5 cores 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