EXERCÍCIOS

INTRODUÇÃO À TEORIA DOS GRAFOS

1O. SEMESTRE DE 2008

1. (i) Prove que

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|, (1)

para quaisquer conjuntos A, B e C finitos. (ii) Sejam dados conjuntos finitos A_{1}, …, A_{n}. Prove que

| ⋃_{1≤i≤n} A_{i}| = ∑_{∅≠J⊂[n]}(−1)^{|J|−1}| ⋂_{j∈J} A_{j}|,  (2)

onde [n] = {1, …, n} e a soma é sobre todos os conjuntos J não-vazios de [n].

{Data de entrega: 11/3/2008}

2. Sejam A_{i} como na Questão 1(ii) acima. Prove que

| ⋃_{1≤i≤n} A_{i}| ≤ ∑_{1≤j≤n} |A_{j}|  (3)

e que

| ⋃_{1≤i≤n} A_{i}| ≥ ∑_{1≤j≤n} |A_{j}| − ∑_{1≤k<ℓ≤n} |A_{k} ∩ A_{ℓ}|.  (4)

3. Quantas partições tem um conjunto com n elementos? Dê as melhores estimativas superiores e inferiores que você conseguir.

4. Para cada natural n, seja P_{n} a ordem parcial cujos elementos são as partes de [n] = {1, …, n} e a relação de ordem é a inclusão. Desenhe o diagrama de Hasse das ordens parciais P_{0}, P_{1}, P_{2}, P_{3} e P_{4}. {Data de entrega: 13/3/2008}

5. Para naturais a ≤ b, seja D(a, b) a ordem parcial sobre os elementos {x ∈ ℕ: a ≤ x ≤ b}, com a relação de ordem ⪯ dada por x ⪯ y se e só se x divide y.

(i) Desenhe o diagrama de Hasse de D(3, 15). (ii) Quais são os elementos maximais de D(3, 15). E os minimais? A

ordem D(3, 15) tem um elemento máximo? Ele tem um elemento mínimo?

(iii) Para quais valores de a e b a ordem D(a, b) tem um elemento mínimo? Para quais valores D(a, b) tem um elemento máximo?

Date: Versão de 2 de junho de 2008.

(iv) Descreva a ordem D(n + 1, 2n) para todo número natural n. {Data de entrega: 13/3/2008}

6. Uma anticadeia em uma ordem parcial P é um subconjunto de P cujos elementos são dois-a-dois incomparáveis.^{1} Determine o tamanho máximo de uma anticadeia na ordem P_{n}, definida na Questão 4.

7. São dados 2n points no espaço. Adicionamos a esta configuração n^{2} + 1 segmentos, conectando estes pontos, de alguma forma arbitrária.^{2} Mostre, dentre os 2n pontos originais, há três deles conectados por segmentos adicionados. {Data de entrega: 13/3/2008}

8. São dados n circunferências desenhadas no plano. Estas circunferências dividem o plano em regiões. Dizemos que duas dessas regiões são adjacentes se eles têm uma fronteira comum (isto é, se um arco de circunferência separa estas regiões). Mostre que é possível colorir estas regiões com duas cores, de forma que quaisquer duas regiões adjacentes têm cores diferentes.

9. (i) Sejam r_{1}, …, r_{n−1} retas no plano (n ≥ 1). Prove que existe uma reta r_{n} no plano que intercepta as n − 1 retas dadas em n − 1 pontos distintos.

(ii) Deduza que L_{n} ≥ L_{n−1}+1 para todo n > 0. Aqui, como visto em sala, L_{n} é o número máximo de regiões em que podemos dividir o plano com n retas.

10. Prove a unicidade no Teorema de Zeckendorf. {Data de entrega: 27/3/2008}

11. Desenhe todos os grafos de ordem 4, a menos de isomorfismo. Isto é, você deve dar a lista completa dos grafos com 4 vértices, sem incluir dois grafos isomorfos (há 11 deles).

12. (i) Desenhe o grafo de Petersen.

(ii) Seja H o grafo linha de K^{5}, o grafo completo de ordem 5 (dessa forma, V (H) = E(K^{5}) e x e y são adjacentes em H se e só se x ∩ y ≠ ∅). Quantos vértices e quantas arestas tem H?

(iii) Seja J o complemento de H.^{3} Desenhe J. (iv) Decida se o grafo de Petersen e o grafo J são isomorfos. Justifique

sua resposta.

13. Seja P = (V, E) o grafo de Petersen.

(i) Um automorfismo de P é simplesmente um isomorfismo σ: V → V de P (isto é, um homomorfismo bijetor cuja inversa σ^{−1} é também um homomorfismo). Descreva 5! = 120 automorfismos de P. {Data de entrega: 27/3/2008}

(ii) [Desafio] O grafo P tem algum outro automorfismo?

1Seja ⪯ uma ordem sobre um conjunto P. Dizemos que x e y são comparáveis (em relação a ⪯) se x ⪯ y ou y ⪯ x; caso nenhuma dessas duas relações valha, dizemos que x e y são incomparáveis.

2Havia um erro de digitação nesta questão. O enunciado agora está correto.

3Assim, dois vértices são adjacentes em J se e só se eles não são adjacentes em H.

14. (i) Existe um homomorfismo do grafo de Petersen P no K^{3}? Justi-

fique sua resposta. (ii) Existe um homomorfismo do grafo de Petersen P no K^{2}? Justi-

fique sua resposta. {Data de entrega: 27/3/2008}

15. Seja g_{n} o número de grafos de ordem n, a menos de isomorfismo. Assim, temos g_{4} = 11 (veja Questão 11). Prove que

\frac{1}{n!}2^{\binom{n}{2}} ≤ g_{n} ≤ 2^{\binom{n}{2}}.  (5)

16. [Desafio] As cotas superior e inferior em (5) são bastante diferentes. Você consegue melhorar alguma dessas cotas significativamente?

17. Um grafo cúbico é um grafo 3-regular (todo vértice tem grau 3). Decida para quais naturais n existe um grafo cúbico de ordem n.

18. [Desafio] Seja G um grafo obtido pela adição de uma aresta a um grafo 4-regular. Assim, se G tem ordem n, ele tem 2n + 1 arestas. Prove que G tem um subgrafo 3-regular.

Uma excelente fonte de exercícios para esta disciplina é o texto Exercícios de Teoria dos Grafos, de Paulo Feofiloff. Veja

       http://www.ime.usp.br/~pf/grafos-exercicios/

Aliás, muitos dos exercícios desta lista serão tirados de lá.

19. Faça o exercício E 2.1.6 do ETG (Exercícios de Teoria dos Grafos). {Data de entrega: 27/3/2008}

20. Seja G um grafo e sejam x e y dois vértices de G.

(i) Seja W = w_{0}w_{1} … w_{k} um x–y passeio em em G (isto é, w_{0} = x e w_{k} = y). Prove que existe um x–y caminho em G que usa somente of vértices que ocorrem em W.

(ii) Suponha que há dois x–y caminhos (distintos) em G. É verdade

que G contém um circuito? (iii) Suponha que há duas x–y trilhas (distintas) em G. É verdade

que G contém um circuito? (iv) Suponha que há dois x–y passeios (distintos) em G. É verdade

que G contém um circuito? {Data de entrega: 3/4/2008}

21. Prove que todo grafo com δ(G) ≥ 3 tem um circuito de comprimento par.

22. Prove que todo grafo conexo contém um caminho de comprimento min{2δ(G), |V (G)| − 1}.

23. Seja G um grafo conexo e dist: V (G) × V (G) → ℝ a função distância associada a G. Prove que valem as seguintes propriedades:

(i) dist(x, y) ≥ 0 para todo x, y ∈ V (G) e dist(x, y) = 0 se e só

se x = y.

(ii) dist(x, y) = dist(y, x) para todo x, y ∈ V (G).

(iii) dist(x, z) ≤ dist(x, y) + dist(y, z) para todo x, y e z ∈ V (G).

24. Seja G um grafo. Prove que quaisquer duas das asserções abaixo implica a terceira:

(i) G é conexo. (ii) G é acíclico. (iii) G tem |V (G)| − 1 arestas. Como são conhecidos os grafos G que satisfazem duas das (e portanto todas as) propriedades acima? {Data de entrega: 3/4/2008}

25. Seja T uma árvore com grau máximo Δ = Δ(T). Mostre que T tem pelo menos Δ folhas. {Data de entrega: 15/4/2008}

26. Seja F uma coleção de subárvores de uma árvore T com a propriedade de que, para quaisquer dois membros T′ e T′′ de F, temos V (T′) ∩ V (T′′) ≠ ∅. Mostre que existe um vértice de T que pertence a todas as árvores em F. {Data de entrega: 15/4/2008}

27. (i) Descreva o algoritmo de busca em profundidade em um grafo. Explique como fica definida uma árvore de busca em profundidade ao executarmos tal busca em um grafo conexo.

(ii) Seja G um grafo conexo e seja r um vértice de G. Suponha que executamos uma busca em profundidade em G, a partir de r. Seja T a árvore de busca em profundidade assim definida. Mostre que T é uma árvore normal com raiz r.

28. Seja T uma árvore e seja a um autormorfismo de T. Mostre que ou (i) existe um vértice x de T tal que a(x) = x ou (ii) existe uma aresta {x, y} tal que a({x, y}) = {x, y}. {Data de entrega: 22/4/2008}

29. Sejam G um grafo e M um emparelhamento em G. Dizemos que um caminho P é um caminho M-alternante se as arestas presentes em P pertencem a M e a E(G)\M, alternadamente. Podemos definir circuitos M-alternantes de forma análoga. Seja agora N um segundo emparelhamento em G. Descreva como é o subgrafo de G gerado pela diferença simétrica M △ N = (M ∪ N) \ (M ∩ N).

30. Sejam G um grafo e M um emparelhamento em G. Mostre que M é de cardinalidade máxima se e só se não existe um caminho Maumentador em G, isto é, um caminho M-alternante com ambos os extremos não-cobertos por M. {Data de entrega: 6/5/2008}.

31. Seja G um grafo bipartido com bipartição (A, B). Para cada X ⊂ A, seja def(X) = |X| − |Γ(X)|. Seja γ = max_{X} def(X), onde o máximo é tomado sobre todo X ⊂ A. Mostre que

ν(G) = |A| − γ.  (6)

[Sugestão. Adicione uma quantiadade adequada de vértices a B, e conecte-os a todos os vértices em A.] {Data de entrega: 6/5/2008}

32. Seja G um grafo bipartido com bipartição (A, B). Mostre que as três asserções abaixo são equivalentes:

(i) G é conexo e cada aresta de G pertence a um emparelhamento perfeito.

(ii) G não é o complemento do K^{2} e, para cada x ∈ A e y ∈ B, o

grafo G − x − y tem um emparelhamento perfeito. (iii) G não é o complemento do K^{2}, |A| = |B|, e, para cada ∅ ≠ X ⊂

A, com X ≠ A, temos |Γ(X)| > |X|. Os grafos bipartidos G satisfazendo (i)–(iii) são conhecidos como grafos bipartidos elementares. {Data de entrega: 6/5/2008}

33. Seja G um grafo bipartido com bipartição (A, B). Suponha que G tem um emparelhamento perfeito e que todo vértice em A tem grau pelo menos k. Mostre que G tem pelo menos k! emparelhamentos perfeitos. {Data de entrega: 6/5/2008}

34. Para cada natural n, considere P_{n}, a ordem parcial das partes de [n], ordenadas por inclusão. Assim, P_{n} tem 2^{n} elementos e x ≤ y se x ⊂ y.

(i) Exiba explicitamente uma anticadeia de tamanho máximo em P_{n}, para 0 ≤ n ≤ 4.

(ii) Escreva P_{n} como uma união de cadeias, para 0 ≤ n ≤ 4, com o

número mínimo possível de cadeias em cada caso. (iii) Argumente cuidadosamente por que suas anticadeias em (i) são

máximas e por que suas decomposições em (ii) são mínimas (usam o número mínimo possível de cadeias).

{Data de entrega: 8/5/2008}

35. Encontre em P_{n} uma anticadeia de cardinalidade \binom{n}{⌊n/2⌋} e encontre uma decomposição de P_{n} nesse mesmo número de cadeias. Deduza que o tamanho máximo de uma anticadeia em P_{n} é \binom{n}{⌊n/2⌋}. \{Data de entrega: 8/5/2008}

36. (i) Prove que todo grafo cúbico sem arestas de corte tem um empa-

relhamento perfeito. (ii) Decida se todo grafo cúbico tem um emparelhamento perfeito.

{Data de entrega: 8/5/2008}

37. Sejam G e H dois grafos. Defina o grafo G∪H como sendo o grafo com conjunto de vértices V (G)∪V (H) e conjunto de arestas E(G)∪E(H). Prove que χ(G ∪ H) ≤ χ(G)χ(H). {Data de entrega: 20/5/2008}

38. Seja G um grafo com n vértices. Suponha que exista uma partição V (G) = V_{1} ∪⋯∪V_{k} de V (G) tal que, para todo i ≠ j, existem x_{i} ∈ V_{i} e x_{j} ∈ V_{j} que não são adjacentes em G. Prove que χ(G) ≤ n − k + 1. {Data de entrega: 20/5/2008}

39. Prove que χ(G) + χ(G^{c}) ≤ n + 1, onde G^{c} é o complemento de G e n = |V (G)|. Prove também que χ(G)χ(G^{c}) ≥ n. {Data de entrega: 20/5/2008}

40. [Desafio] Prove ou desprove: existe uma função f tal que, para todo grafo G, temos χ(G) ≤ f(ω(G)).

41. Seja G um grafo e 0 ≤ β ≤ 1 um número real. Dizemos que G tem a propriedade P (β) se, para todo subgrafo H de G, temos que α(H) ≥ β|V (H)|, onde, como de usual, α(H) é o número de independência de H. Prove que um grafo G que satisfaz P (1/2) é bipartido. {Data de entrega: 27/5/2008}

42. [Desafio] Prove ou desprove: um grafo G que satisfaz P (1/3) satisfaz χ(G) ≤ 10^{10}. (Veja a Questão 41.) Seguindo a mesma linha, prove ou desprove: se G satisfaz P (\frac{1}{2} − 10^{−6}), então χ(G) ≤ 10^{10^{10}}.

43. Prove que ‘quase todo’ grafo conexo G com n vértices é tal que α(G) ≥ n/Δ(G). Para quais G essa relação não vale? Encontre uma relação desse gênero que vale para todo grafo G. {Data de entrega: 27/5/2008}

44. Determine o índice cromático do grafo completo K^{n}, para todo valor de n. {Data de entrega: 27/5/2008}

45. Seja G um grafo. Suponha que, para todo v ∈ V (G), temos um conjunto de cores disponíveis S(v) para v. Queremos encontrar uma coloração própria dos vértices de G, digamos f: V (G) → S, onde S = ⋃_{v∈V (G)} S(v), de forma que f(v) ∈ S(v) para todo v ∈ V (G). Em palavras: queremos uma coloração própria dos vértices de G que usa, em cada vértice, uma das cores disponíveis para ele. Seja s o menor inteiro com a seguinte propriedade: para quaisquer conjuntos S(v) (v ∈ V (G)) com |S(v)| ≥ s para todo v, existe uma coloração própria f como exigido acima. Chamamos tal s de número de escolha de G, e o denotamos por ch(G).

(i) Mostre que ch(G) ≥ χ(G). (ii) Decida se, para todo grafo G, temos ch(G) = χ(G). {Data de entrega: 5/6/2008}

46. Seja m um inteiro positivo e considere U = [2m−1] = {1, …, 2m−1}. Denotamos por X = \binom{U}{m} o conjunto de todos os subconjuntos de cardinalidade m de U. Sejam X_{0} e X_{1} duas ‘cópias disjuntas’ de X (podemos formalizar isso pondo X_{0} = X × {0} e X_{1} = X × {1}). Considere o grafo bipartido completo B com conjunto de vértices V = X_{0} ∪ X_{1} e com todo vértice em X_{0} adjacente a todo vértice em X_{1}.

(i) Prove que ch(B) ≥ m + 1. (ii) Conclua que existem grafos bipartidos G com n vértices satisfa-

zendo ch(G) > (1/2) log_{2} n. {Data de entrega: 5/6/2008}

47. [Desafio] Seja B um grafo bipartido, com bipartição V (B) = U ∪ W. Suponha que |U| = |W | = n. Mostre que ch(B) ≤ log_{2}(4n). [Sugestão. Sejam S(v) (v ∈ V (B)) com |S(v)| ≥ s = ⌊log_{2} n⌋ + 2 > log_{2} n + 1. Seja S = ⋃_{v∈V (G)} S(v). Considere uma partição aleatória S = A ∪ B de S, escolhendo para A um subconjunto de S sorteado uniformemente ao acaso (isto é, todos os subconjuntos de S têm a mesma probabilidade de serem escolhidos). Equivalentemente, cada elemento c ∈ S está em A com probabilidade 1/2, e todos esses eventos são independentes. Use as cores em A para colorir os vértices em U e use as cores em B para colorir os vértices em W. Note que basta que, para cada u ∈ U, tenhamos A ∩ S(u) ≠ ∅ e que para cada w ∈ W, tenhamos B ∩ S(w) ≠ ∅.]

48. Seja G um grafo com seqüência de graus d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} (n ≥ 3). (i) Mostre que se d_{k} > k para todo k < n/2, então G é hamiltoniano. (ii) Suponha que se d_{k} ≤ k e d_{l} ≤ l, então d_{k} + d_{l} ≥ n (k ≠ l).

Mostre que G é hamiltoniano. {Data de entrega: 10/6/2008}

49. Seja G um grafo n-regular com 2n + 1 vértices.

(i) Mostre que G tem um circuito de comprimento pelo menos 2n. (ii) Mostre que G é hamiltoniano. {Data de entrega: 10/6/2008}