Lista07_MD_Grafos

Prévia do material em texto

VII	
  Lista	
  de	
  Exercícios	
  –	
  Matemática	
  Discreta	
  
Grafos	
  
	
  	
  	
  	
   	
  
	
  	
  
	
  
Unidades de Entrada Nível Oculto
Seção 5.1 Terminologia e Aplicações de Grafos 235
Unidades de Saída
•Figura 5.32
Revisão da Seção 5.1
Técnicas
• Usar da terminologia de grafos
• Mostrar que dois grafos são ou não isomorfos
• Encontrar uma representação plana de um grafo simples ou demonstrar que não existe tal representação
• Encontrar o número cromático de um grafo
• Construir árvores para expressões
Idéia Principal
Diversas situações podem ser representadas através de grafos.
Exercícios 5.1
1. Responda as seguintes perguntas sobre o grafo mostrado a seguir:
a. Este grafo é simples?
b. Este grafo é completo?
Exercício 1
236 Gratos e Árvores
c . Este grafo é conexo?
d. Existem dois caminhos entre os vértices 3 e 6?
e. Este grafo possui algum ciclo?
f. O grafo possui algum vértice cuja remoção o tornaria uma árvore?
g. O grafo possui algum vértice cuja remoção o tornaria desconexo?
2. Esboce uma figura para cada um dos seguintes grafos:
a. um grafo simples com três vértices, cada qual com grau 2
b. quatro vértices, com ciclos de tamanho 1, 2, 3 e 4
c. uma árvore com cinco vértices e altura 1
3. Responda as perguntas a seguir sobre a árvore abaixo com o vértice a como raiz.
a. Ela é uma árvore binária?
b. Ela é uma árvore binária completa?
c. Qual o pai do vértice e?
d. Qual é o filho à esquerda do vértice e?
e. Qual a altura de g?
f. Qual é a altura da árvore?
Exercício 3
4. Use o grafo direcionado da figura a seguir para responder as perguntas abaixo
a. Quais vértices são alcançáveis a partir do vértice 3?
b. Qual é o comprimento do menor caminho entre 3 e 6?
c. Qual é o caminho do vértice 1 ao vértice 6 com comprimento 8?
Exercício 4
5. a. Desenhe K6. b. Desenhe K3,4.
6. Para cada uma das características a seguir, desenhe um grafo ou explique por que um grafo com as
características pedidas não existe.
a. Quatro vértices de graus 1, 2, 3 e 4, respectivamente.
b. Simples com quatro vértices de graus 1, 2, 3 e 4, respectivamente.
c. Quatro vértices de graus 2, 3, 3 e 4, respectivamente.
d. Quatro vértices de graus 2, 3, 3 e 3, respectivamente.
7. Qual dos grafos na figura abaixo não é isomorfo aos outros? Por quê?
Seção 5.1 Terminologia e Aplicações de Grafos 237
(a) (b) (c)
Exercício 7
8. Qual dos grafos na figura abaixo não é isomorfo aos outros? Por quê?
(e)(d)(c)
Exercício 8
(b)(a)
Para os Exercícios 9 a 14, diga se os dois grafos apresentados são ou não isomorfos. Se forem, apresente
a função que estabelece o isomorfismo entre eles; caso contrário, explique por quê.
10.
(a) (b)
(a) (b)
	
  Fig	
  exercício	
  1	
  
	
  
	
  
Seção 5.1 Terminologia e Aplicações de Grafos 237
(a) (b) (c)
Exercício 7
8. Qual dos grafos na figura abaixo não é isomorfo aos outros? Por quê?
(e)(d)(c)
Exercício 8
(b)(a)
Para os Exercícios 9 a 14, diga se os dois grafos apresentados são ou não isomorfos. Se forem, apresente
a função que estabelece o isomorfismo entre eles; caso contrário, explique por quê.
10.
(a) (b)
(a) (b)
11.
12.
238 Grafos e Árvores
(a) (b)
(a) (b)
14.
(a) (b)
(a) (b)
	
  	
  	
  
	
  
11.
12.
238 Grafos e Árvores
(a) (b)
(a) (b)
14.
(a) (b)
(a) (b)
Seção 5.1 Terminologia e Aplicações de Grafos 239
15. Demonstre que dois grafos não são isomorfos se:
a. um deles tem mais vértices que o outro
b. um deles tem mais arestas que o outro
c. um deles tem arestas paralelas, e o outro não tem
d. um deles tem um laço e o outro não tem
e. um deles tem um vértice de grau k, e o outro não tem
f. um deles é conexo, e o outro não é
g. um deles tem um ciclo, e o outro não tem
16. Desenhe todos os grafos não-isomorfos, simples com dois vértices.
17. Desenhe todos os grafos não-isomorfos, simples com três vértices.
18. Desenhe todos os grafos não-isomorfos, simples com quatro vértices.
19. Encontre uma expressão para o número de arestas de Kn e demonstre que a expressão que você encontrou
está correta.
20. Verifique a fórmula de Euler para o grafo simples, conexo e planar da Fig. 5.21.
21. Demonstre que K2,3 é um grafo planar.
22. Demonstre que o grafo a seguir é um grafo planar.
23. Se um grafo simples, conexo e planar tem seis vértices, todos de grau 3, em quantas regiões ele divide o
plano?
24. Se todos os vértices de um grafo simples, conexo e planar têm grau 4 e o número de arestas é 12, em quantas
regiões ele divide o plano?
25. A fórmula de Euler (equação (1) do teorema sobre o número de vértices e de arestas) aplica-se a grafos
que não sejam simples? E as desigualdades (2) e (3) do mesmo teorema?
26. O que está errado no argumento a seguir que visa tornar um grafo não-planar em um grafo planar através
de subdivisões?
Em um grafo não-planar existem duas arestas ai e aj que se intersectam em um ponto v que não é um
vértice. Faça uma subdivisão elementar de a1 com a inserção de um vértice em v e uma subdivisão ele-
mentar de a2 com a inserção de um vértice em v. No grafo resultante, o ponto de interseção é um vértice.
Repita este processo com todas as interseções que ocorram fora de vértices; o grafo resultante não será
planar.
Nos Exercícios 27 a 30, determine se o grafo é planar (mostrando uma representação planar) ou não-planar
(encontrando um subgrafo homeomorfo a K5 ou K3,3.
Exercício 1
Seção 5.1 Terminologia e Aplicações de Grafos 239
15. Demonstre que dois grafos não são isomorfos se:
a. um deles tem mais vértices que o outro
b. um deles tem mais arestas que o outro
c. um deles tem arestas paralelas, e o outro não tem
d. um deles tem um laço e o outro não tem
e. um deles tem um vértice de grau k, e o outro não tem
f. um deles é conexo, e o outro não é
g. um deles tem um ciclo, e o outro não tem
16. Desenhe todos os grafos não-isomorfos, simples com dois vértices.
17. Desenhe todos os grafos não-isomorfos, simples com três vértices.
18. Desenhe todos os grafos não-isomorfos, simples com quatro vértices.
19. Encontre uma expressão para o número de arestas de Kn e demonstre que a expressão que você encontrou
está correta.
20. Verifique a fórmula de Euler para o grafo simples, conexo e planar da Fig. 5.21.
21. Demonstre que K2,3 é um grafo planar.
22. Demonstre que o grafo a seguir é um grafo planar.
23. Se um grafo simples, conexo e planar tem seis vértices, todos de grau 3, em quantas regiões ele divide o
plano?
24. Se todos os vértices de um grafo simples, conexo e planar têm grau 4 e o número de arestas é 12, em quantas
regiões ele divide o plano?
25. A fórmula de Euler (equação (1) do teorema sobre o número de vértices e de arestas) aplica-se a grafos
que não sejam simples? E as desigualdades (2) e (3) do mesmo teorema?
26. O que está errado no argumento a seguir que visa tornar um grafo não-planar em um grafo planar através
de subdivisões?
Em um grafo não-planar existem duas arestas ai e aj que se intersectam em um ponto v que não é um
vértice. Faça uma subdivisão elementar de a1 com a inserção de um vértice em v e uma subdivisão ele-
mentar de a2 com a inserção de um vértice em v. No grafo resultante, o ponto de interseção é um vértice.
Repita este processo com todas as interseções que ocorram fora de vértices; o grafo resultante não será
planar.
Nos Exercícios 27 a 30, determine se o grafo é planar (mostrando uma representação planar) ou não-planar
(encontrando um subgrafo homeomorfo a K5 ou K3,3.
Exercício 1
	
  
	
  
	
  
	
  	
  	
  
	
  
Seção 5.1 Terminologia e Aplicações de Grafos 239
15. Demonstre que dois grafos não são isomorfos se:
a. um deles tem mais vértices que o outro
b. um deles tem mais arestas que o outro
c. um deles tem arestas paralelas, e o outro não tem
d.um deles tem um laço e o outro não tem
e. um deles tem um vértice de grau k, e o outro não tem
f. um deles é conexo, e o outro não é
g. um deles tem um ciclo, e o outro não tem
16. Desenhe todos os grafos não-isomorfos, simples com dois vértices.
17. Desenhe todos os grafos não-isomorfos, simples com três vértices.
18. Desenhe todos os grafos não-isomorfos, simples com quatro vértices.
19. Encontre uma expressão para o número de arestas de Kn e demonstre que a expressão que você encontrou
está correta.
20. Verifique a fórmula de Euler para o grafo simples, conexo e planar da Fig. 5.21.
21. Demonstre que K2,3 é um grafo planar.
22. Demonstre que o grafo a seguir é um grafo planar.
23. Se um grafo simples, conexo e planar tem seis vértices, todos de grau 3, em quantas regiões ele divide o
plano?
24. Se todos os vértices de um grafo simples, conexo e planar têm grau 4 e o número de arestas é 12, em quantas
regiões ele divide o plano?
25. A fórmula de Euler (equação (1) do teorema sobre o número de vértices e de arestas) aplica-se a grafos
que não sejam simples? E as desigualdades (2) e (3) do mesmo teorema?
26. O que está errado no argumento a seguir que visa tornar um grafo não-planar em um grafo planar através
de subdivisões?
Em um grafo não-planar existem duas arestas ai e aj que se intersectam em um ponto v que não é um
vértice. Faça uma subdivisão elementar de a1 com a inserção de um vértice em v e uma subdivisão ele-
mentar de a2 com a inserção de um vértice em v. No grafo resultante, o ponto de interseção é um vértice.
Repita este processo com todas as interseções que ocorram fora de vértices; o grafo resultante não será
planar.
Nos Exercícios 27 a 30, determine se o grafo é planar (mostrando uma representação planar) ou não-planar
(encontrando um subgrafo homeomorfo a K5 ou K3,3.
Exercício 1
Exercício 37
240 Grafos e Árvores
28.
30.
Os Exercícios 31 a 36 referem-se ao complemento de um grafo. Se G é um grafo simples, o complemento de
G, denotado por G' é o grafo simples com o mesmo conjunto de vértices, onde os vértices x — y são adjacentes
em G' se, e somente se, eles não são adjacentes em G.
31. Desenhe G' para o grafo da Fig. 5.9a.
32. Desenhe K'4.
33. Mostre que se dois grafos simples G1 e G2 são isomorfos, então seus complementos G'1 e G'2 também o são.
34. Um grafo simples é autocomplementar se for isomorfo ao seu complementar. Demonstre que em um
grafo autocomplementar com n vértices (n > 1), n = 4k ou n = 4k + 1 para algum inteiro k. (Dica: Use
o resultado do Exercício 19.)
35. a. Demonstre que em qualquer grafo simples G com pelo menos dois vértices, se G não for conexo, então
G' é conexo. (Dica: Se G não é conexo, então G consiste em uma coleção de subgrafos conexos "dis-
juntos".)
b. Encontre um grafo G onde tanto G quanto G' são conexos, mostrando, assim, que a recíproca do item
(a) é falsa.
36. Demonstre que se em um grafo simples e conexo, então G e G' não podem ser ambos planares.
37. Desenhe o grafo dual do mapa da figura abaixo.
Exercício 37
240 Grafos e Árvores
28.
30.
Os Exercícios 31 a 36 referem-se ao complemento de um grafo. Se G é um grafo simples, o complemento de
G, denotado por G' é o grafo simples com o mesmo conjunto de vértices, onde os vértices x — y são adjacentes
em G' se, e somente se, eles não são adjacentes em G.
31. Desenhe G' para o grafo da Fig. 5.9a.
32. Desenhe K'4.
33. Mostre que se dois grafos simples G1 e G2 são isomorfos, então seus complementos G'1 e G'2 também o são.
34. Um grafo simples é autocomplementar se for isomorfo ao seu complementar. Demonstre que em um
grafo autocomplementar com n vértices (n > 1), n = 4k ou n = 4k + 1 para algum inteiro k. (Dica: Use
o resultado do Exercício 19.)
35. a. Demonstre que em qualquer grafo simples G com pelo menos dois vértices, se G não for conexo, então
G' é conexo. (Dica: Se G não é conexo, então G consiste em uma coleção de subgrafos conexos "dis-
juntos".)
b. Encontre um grafo G onde tanto G quanto G' são conexos, mostrando, assim, que a recíproca do item
(a) é falsa.
36. Demonstre que se em um grafo simples e conexo, então G e G' não podem ser ambos planares.
37. Desenhe o grafo dual do mapa da figura abaixo.
Seção 5.1 Terminologia e Aplicações de Grafos 241
38. Desenhe um mapa para o qual o grafo da figura a seguir sirva como grafo dual.
Exercício 38
Nos Exercícios 39 a 42, encontre o número cromático de cada grafo.
40.
41. Kn
42. Km,n
43. O teorema das seis cores pode ser provado sem usar o grafo dual de um mapa. No lugar disto, tornamos
as fronteiras das regiões retas, de forma que o problema da coloração do mapa mostrado na parte (a) da
figura a seguir seja representado pelo grafo da parte (b) da mesma figura. Primeiro admitimos que nenhum
país tenha um buraco no meio. Por isso, o grafo não terá laços, será planar e conexo. Além disso, todo
vértice terá ao menos grau 3.
(a)
Exercício 43
(b)
a. Mostre que podemos considerar o grafo como simples mostrando que se seis cores são o suficiente
para colorir um grafo simples, elas serão suficientes para um grafo com arestas paralelas também.
(Dica: Imagine países pequenos nos vértices temporariamente.)
b. Demonstre que, em um grafo simples, conexo e planar com R regiões fechadas, n — a + R = 1.
c. Considere um grafo simples, conexo e planar, e admita que toda região fechada tem pelo menos seis
Seção 5.1 Terminologia e Aplicações de Grafos 241
38. Desenhe um mapa para o qual o grafo da figura a seguir sirva como grafo dual.
Exercício 38
Nos Exercícios 39 a 42, encontre o número cromático de cada grafo.
40.
41. Kn
42. Km,n
43. O teorema das seis cores pode ser provado sem usar o grafo dual de um mapa. No lugar disto, tornamos
as fronteiras das regiões retas, de forma que o problema da coloração do mapa mostrado na parte (a) da
figura a seguir seja representado pelo grafo da parte (b) da mesma figura. Primeiro admitimos que nenhum
país tenha um buraco no meio. Por isso, o grafo não terá laços, será planar e conexo. Além disso, todo
vértice terá ao menos grau 3.
(a)
Exercício 43
(b)
a. Mostre que podemos considerar o grafo como simples mostrando que se seis cores são o suficiente
para colorir um grafo simples, elas serão suficientes para um grafo com arestas paralelas também.
(Dica: Imagine países pequenos nos vértices temporariamente.)
b. Demonstre que, em um grafo simples, conexo e planar com R regiões fechadas, n — a + R = 1.
c. Considere um grafo simples, conexo e planar, e admita que toda região fechada tem pelo menos seis
	
  
	
  	
  
	
  	
  Exercícios	
  retirados	
  do	
  capítulo	
  5	
  do	
  livro	
  “Fundamentos	
  Matemáticos	
  para	
  a	
  Ciência	
  da	
  Computação“,	
  3a	
  Edicão,	
  Judith	
  L.	
  Gersting,	
  LTC.	
  	
  Algumas	
  respostas...	
  
	
  
Seção 5.1 Terminologia e Aplicações de Grafos 241
38. Desenhe um mapa para o qual o grafo da figura a seguir sirva como grafo dual.
Exercício 38
Nos Exercícios 39 a 42, encontre o número cromático de cada grafo.
40.
41. Kn
42. Km,n
43. O teorema das seis cores pode ser provado sem usar o grafo dual de um mapa. No lugar disto, tornamos
as fronteiras das regiões retas, de forma que o problema da coloração do mapa mostrado na parte (a) da
figura a seguir seja representado pelo grafo da parte (b) da mesma figura. Primeiro admitimos que nenhum
país tenha um buraco no meio. Por isso, o grafo não terá laços, será planar e conexo. Além disso, todo
vértice terá ao menos grau 3.
(a)
Exercício 43
(b)
a. Mostre que podemos considerar o grafo como simples mostrando que se seis cores são o suficiente
para colorir um grafo simples, elas serão suficientes para um grafo com arestas paralelas também.
(Dica: Imagine países pequenos nos vértices temporariamente.)
b. Demonstre que, em um grafo simples,conexo e planar com R regiões fechadas, n — a + R = 1.
c. Considere um grafo simples, conexo e planar, e admita que toda região fechada tem pelo menos seis
242 Grafos e Árvores
arestas adjacentes a ela. Mostre que
d. Considere agora um grafo simples, conexo e planar onde todos os vértices têm grau pelo menos 3.
Mostre que este tipo de grafo tem pelo menos uma região fechada com não mais do que cinco arestas
adjacentes.
e. Demonstre que seis cores são suficientes para colorir qualquer mapa plano onde nenhum país tenha
um buraco no meio.
f. Demonstre que seis cores são suficientes para colorir qualquer mapa plano. (Dica: Retire algumas
fendas temporariamente do mapa.)
44. Cinco lobistas políticos estão visitando sete membros do Congresso (chamados de A a G) no mesmo dia.
Os membros do Congresso que os cinco lobistas precisam visitar são:
1: A, B, D
2:B,C, F
3: A, B, D, G
4:E, G
5: D, E, F
Cada membro do Congresso estará disponível por uma hora. Qual o menor número de intervalos de visita
que deve ser usado a fim de que não haja conflitos entre os lobistas? (Dica: Trate isto como um problema
de coloração de grafos.) O que ocorreria se o lobista 3 descobrisse que não precisa visitar o membro B,
e o lobista 5 descobrisse que não precisa visitar o membro D?
Nos Exercícios 45 a 48, desenhe a árvore da expressão.
45. [(x - 2) * 3] + (5 + 4)
46. [(2 * x - 3 *y) + 4 * z] + 1
47. 1 - (2 - [3 - (4 - 5)])
48. [(6 2) * 4] + [(1 + x) * (5 + 3)]
49. Demonstre que em qualquer grafo simples G com n vértices e a arestas,
50. Demonstre que um grafo simples e conexo com n vértices tem pelo menos n — 1 arestas. (Dica: Mostre
que isto pode ser tratado como um problema do tipo "Um grafo simples e conexo com m arestas tem, no
máximo, m + 1 vértices." E então use indução em m.)
51. Demonstre que um grafo simples com n vértices e mais de C (n — 1,2) arestas é conexo. (Dica:
Use os Exercícios 35 e 50.)
52. Demonstre que uma árvore com n vértices, tem pelo menos dois vértices de grau 1.
53. Demonstre que um grafo simples é uma árvore não-enraizada se, e somente se, existir um único caminho
entre quaisquer dois vértices.
54. Seja G um grafo simples. Demonstre que G é uma árvore não-enraizada se, e somente se, G for conexo
e a remoção de qualquer aresta sua o tornar desconexo.
55. Seja G um grafo simples. Demonstre que G é uma árvore não-enraizada se, e somente se, a inclusão de
uma aresta tornar G um grafo com exatamente um ciclo.
56. Demonstre que uma árvore binária tem no máximo 2d vértices em seu nível d.
57. a. Desenhe uma árvore binária completa de altura 2. Quantos vértices ela tem?
b. Desenhe uma árvore binária completa de altura 3. Quantos vértices ela tem?
c. Formule uma conjectura sobre quantos vértices tem uma árvore binária completa de altura h.
d. Demonstre sua conjectura. (Dica: Use o Exercício 56.)
58. Demonstre que uma árvore binária completa com x vértices internos tem x + 1 folhas.
59. Demonstre que o número de folhas de uma árvore binária é 1 mais o número de vértices com dois filhos.
242 Grafos e Árvores
arestas adjacentes a ela. Mostre que
d. Considere agora um grafo simples, conexo e planar onde todos os vértices têm grau pelo menos 3.
Mostre que este tipo de grafo tem pelo menos uma região fechada com não mais do que cinco arestas
adjacentes.
e. Demonstre que seis cores são suficientes para colorir qualquer mapa plano onde nenhum país tenha
um buraco no meio.
f. Demonstre que seis cores são suficientes para colorir qualquer mapa plano. (Dica: Retire algumas
fendas temporariamente do mapa.)
44. Cinco lobistas políticos estão visitando sete membros do Congresso (chamados de A a G) no mesmo dia.
Os membros do Congresso que os cinco lobistas precisam visitar são:
1: A, B, D
2:B,C, F
3: A, B, D, G
4:E, G
5: D, E, F
Cada membro do Congresso estará disponível por uma hora. Qual o menor número de intervalos de visita
que deve ser usado a fim de que não haja conflitos entre os lobistas? (Dica: Trate isto como um problema
de coloração de grafos.) O que ocorreria se o lobista 3 descobrisse que não precisa visitar o membro B,
e o lobista 5 descobrisse que não precisa visitar o membro D?
Nos Exercícios 45 a 48, desenhe a árvore da expressão.
45. [(x - 2) * 3] + (5 + 4)
46. [(2 * x - 3 *y) + 4 * z] + 1
47. 1 - (2 - [3 - (4 - 5)])
48. [(6 2) * 4] + [(1 + x) * (5 + 3)]
49. Demonstre que em qualquer grafo simples G com n vértices e a arestas,
50. Demonstre que um grafo simples e conexo com n vértices tem pelo menos n — 1 arestas. (Dica: Mostre
que isto pode ser tratado como um problema do tipo "Um grafo simples e conexo com m arestas tem, no
máximo, m + 1 vértices." E então use indução em m.)
51. Demonstre que um grafo simples com n vértices e mais de C (n — 1,2) arestas é conexo. (Dica:
Use os Exercícios 35 e 50.)
52. Demonstre que uma árvore com n vértices, tem pelo menos dois vértices de grau 1.
53. Demonstre que um grafo simples é uma árvore não-enraizada se, e somente se, existir um único caminho
entre quaisquer dois vértices.
54. Seja G um grafo simples. Demonstre que G é uma árvore não-enraizada se, e somente se, G for conexo
e a remoção de qualquer aresta sua o tornar desconexo.
55. Seja G um grafo simples. Demonstre que G é uma árvore não-enraizada se, e somente se, a inclusão de
uma aresta tornar G um grafo com exatamente um ciclo.
56. Demonstre que uma árvore binária tem no máximo 2d vértices em seu nível d.
57. a. Desenhe uma árvore binária completa de altura 2. Quantos vértices ela tem?
b. Desenhe uma árvore binária completa de altura 3. Quantos vértices ela tem?
c. Formule uma conjectura sobre quantos vértices tem uma árvore binária completa de altura h.
d. Demonstre sua conjectura. (Dica: Use o Exercício 56.)
58. Demonstre que uma árvore binária completa com x vértices internos tem x + 1 folhas.
59. Demonstre que o número de folhas de uma árvore binária é 1 mais o número de vértices com dois filhos.
Respostas dos Exercícios Selecionados 487
AXB = BxA =
Mas esses valores são iguais, porque aik = akj e akj = ajk (A é simétrica)
Capítulo 5
Exercícios 5.1
b. Por exemplo: c.2. a.
4. a. 4,5,6
b. Comprimento 2
c. Por exemplo (rotulando os vértices): 1,2, 1,2, 2, 1,4,5, 6
7. b. Grafo (b) porque não tem vértice de grau 0.
13. Não isomorfo; o grafo em (b) tem um vértice de grau 5, o grafo em (a) não tem.
16. 21.
23. 5 (pela fórmula de Euler)
27. Planar
	
  	
  	
   	
  
	
  	
  	
  	
  	
  	
  39.	
  3	
  
	
  	
  
Respostas dos Exercícios Selecionados 487
AXB = BxA =
Mas esses valores são iguais, porque aik = akj e akj = ajk (A é simétrica)
Capítulo 5
Exercícios 5.1
b. Por exemplo: c.2. a.
4. a. 4,5,6
b. Comprimento 2
c. Por exemplo (rotulando os vértices): 1,2, 1,2, 2, 1,4,5, 6
7. b. Grafo (b) porque não tem vértice de grau 0.
13. Não isomorfo; o grafo em (b) tem um vértice de grau 5, o grafo em (a) não tem.
16. 21.
23. 5 (pela fórmula de Euler)
27. Planar
488 Respostas dos Exercícios Selecionados
29. Não-planar; o subgrafo abaixo pode ser obtido a partir de K3,3 através de subdivisões elementares.
31.
35. a. Se G é desconexo, então G consiste em dois ou mais subgrafos conexos que não tenham caminho en-
tre eles. Seja x e y vértices distintos. Se x e y estão em subgrafos diferentes, então não há nenhuma
aresta x-y em G; portanto, existe uma aresta x-y em G' e existe um caminho de x a y em G'. Se x e y
estão no mesmo subgrafo, então pegue um vértice z em um subgrafo diferente. Existe uma aresta x-z
e uma aresta z-y em G'; portanto existe um caminho de x a y em G'.
b.
G G'
39. 3
43. a. Um grafo com arestas paralelas deve conter
Crie, temporariamente, pequenos países nos vértices das arestas paralelas, obtendo
que é um grafo simples. Qualquer coloração que satisfaça este grafo satisfaz o grafo original (fazendoas
regiões se transformarem em pontos).
46.
488 Respostas dos Exercícios Selecionados
29. Não-planar; o subgrafo abaixo pode ser obtido a partir de K3,3 através de subdivisões elementares.
31.
35. a. Se G é desconexo, então G consiste em dois ou mais subgrafos conexos que não tenham caminho en-
tre eles. Seja x e y vértices distintos. Se x e y estão em subgrafos diferentes, então não há nenhuma
aresta x-y em G; portanto, existe uma aresta x-y em G' e existe um caminho de x a y em G'. Se x e y
estão no mesmo subgrafo, então pegue um vértice z em um subgrafo diferente. Existe uma aresta x-z
e uma aresta z-y em G'; portanto existe um caminho de x a y em G'.
b.
G G'
39. 3
43. a. Um grafo com arestas paralelas deve conter
Crie, temporariamente, pequenos países nos vértices das arestas paralelas, obtendo
que é um grafo simples. Qualquer coloração que satisfaça este grafo satisfaz o grafo original (fazendo as
regiões se transformarem em pontos).
46.