Lista de Exercícios Resolvidos - Teoria dos Grafos e Isomorfismo

1 Dado um grafo G VE O grafo de linha LG de G é o grafo que satisfaz VLG EG e e1e2 ELG se e somente se e1 uv e e2 vw para alguma tripla de vértices u v w de V e uv vw E a Determine os grafos de linha de K4 Cn Q3 Petersen O grafo da esquerda da figura 1a Pn Sn Wn b Dê o número de arestas no grafo de linha LG em função dos graus dos vértices de G 2 Se o diâmetro de G é maior que 3 então o diâmetro de G é menor que 3 3 Um grafo G é autocomplementar se G e seu complemento são isomorfos a Mostre que se G é autocomplementar então V 4k ou V 4k 1 para algum k inteiro não negativo b Se G é autocomplementar então o diâmetro de G é menor ou igual a 3 c Mostre que se G é auto complementar e n 4k 1 então existe v V tal que dv 2k 4 Mostre que dois caminhos máximos em um grafo conexo SEMPRE possuem pelo menos um vértice em comum 5 Prove ou disprove que os seguintes pares de grafos são isomorfos Figure 1 Grafo G e grafo H Figure 2 Grafo G e grafo H Figure 3 Grafo G e grafo H 6 Justifique e dê os valores de αG o número de independência o tamanho do maior conjunto independente de vértices de G βG o número de independência do grafo de linha ou o tamanho do emparelhamento máximo o tamanho do maior conjunto independente de arestas de G ω o número de clique o tamanho da maior clique de G V E se é regular quando é regular a Kn b Knm c Cn d Pn e Wn f Qn g Petersen h Árvore 7 Prove ou dê contraexemplo c Se G é um grafo com δ 4 então existe um ciclo de comprimento maior ou igual a 5 d Se H é subgrafo de G então χG χH e Se H é subgrafo de G então ωG ωH f Em todo grafo o número de vértices de grau ímpar é par g Em todo grafo o número de vértices de grau par é ímpar 8 Prove o Teorema da Amizade em qualquer festa com pelo menos seis pessoas ou três se conhecem mutuamente ou três não se conhecem mutuamente 9 Suponha que G é um grafo sem vértices de grau zero e sem subgrafos induzidos contendo duas arestas Prove que G é um grafo completo 10 Prove ou refute se G é um grafo contendo exatamente dois vértices de grau ímpar então existe necessariamente um caminho ligando estes dois vértices em G 11 Uma sequência d d1 d2 d3 dn é gráfica se existe um grafo cuja a sequência dos graus de seus vértices é d Mostre que as sequências 7 6 5 4 3 3 2 e 6 6 5 4 3 3 1 não são gráficas 12 Determine todos os grafos não isomorfos com 5 vértices e 7 arestas 13 A função distância satisfaz a desigualdade triangular 14 Dê uma descrição para as matrizes de adjacências dos grafos das classes especiais estudadas Kn Kn1n2 Sn Pn Cn Wn Qnm Mux 15 Dizemos que uma face de um polígono A intersecta uma face B se elas compartilham uma aresta É possível desenhar 5 quadriláteros tais que cada um deles a intersectem 1 ou 3 outros quadriláteros b intersectem 1 ou 4 outros quadriláteros 16 Dado um grafo G VE e ωG o tamanho do maior completo subgrafo de G mostre que ωG χ Δ 1 Dê duas classes de grafos nas quais χ Δ 1 17 Mostre o teorema das 6 cores isto é se G é planar então G é 6 colorível 18 Mostre que em todo grafo G VE colorido com χG cores satisfaz que para cada cor c 1 2 3 x existe um vértice v V tal que para toda cor c diferente da cor cv de v existe um vizinho de v com a cor c 19 Dado um grafo G VE e k N uma kcoloração das arestas de G é uma função f E 1 2 3 k tal que fuv fuw O índice cromático χG é o menor k tal que G tem uma kcoloração de arestas Determine a χK3 b χK4 c χK5 d χPetersen e χKn f χWn g χCn h χQ3 20 Dado um grafo G VE δ Δ serem respectivamente o grau mínimo e máximo de G Determine os valores possíveis de χG