Conjunto Independente Maximo em Florestas e 3-Coloracao - Problemas em Grafos

3 PROBLEMA DO CONJUNTO INDEPENDENTE MÁXIMO EM FLORESTAS Entrada uma F uma floresta um grafo no qual toda componente conexa é uma árvore Saída o maior tamanho de um conjunto independente em F que denotamos por αF a Seja F uma floresta e seja S um conjunto independente máximo de F Prove que se u S então S u é um conjunto independente máximo de F NFu onde NFu NFu u b Prove que se u F tal que dFu 1 e S é um conjunto independente máximo de F NFu então S u é um conjunto independente máximo de F 6 Seja G um grafo Uma coloração de G é uma função c VG 1 2 k para algum inteiro k 1 tal que cu cv para toda aresta uv EG Ela recebe esse nome pois pode ser visualizada como uma atribuição de cores aos vértices cada inteiro entre 1 e k é uma cor Uma 3coloração é uma coloração em que k 3 Considere o problema da 3coloração dado um grafo G determinar se ele tem ou não uma 3coloração Mostre que o problema da 3coloração está em NP