P3 - 2023-1

Fabio Ribeiro Junho 2023 QUESTOES DE 1,0 PONTO 1. Seja A = {2,3,5,7, 21,42, 105, 210}. Considere a relacéo x|y em A. Indi- que os elementos minimo, minimais, maximos e maximais. 2. Seja K,, o grafo completo com n vértices. Mostre que 0 nimero de arestas 2 n(n-1 e nnd) 3. Seja G um grafo. Definimos o grau de x € V(G) por d(x) = |{xy;ry € E(G)}| Mostre que S> d(v) = 2|E(G). veEV(G) 4. Mostre que todo grafo G possui um ntimero par de vértices de grau impar. 5. Seja G um grafo. Definimos 0 grau minimo e o grau maximo de G, res- pectivamente, por 6 = min{d(x);x € V(G)} A= mar{d(x);x € V(G)} Mostre que |E(G)| 6<2——— <A. IV(G)| 1 QUEST˜OES DE 2,0 PONTO 6. Se dois v´ertices x e y num grafo est˜ao conectados, a distˆancia entre x e y, indicada por dG(x, y), ´e o comprimento do menor caminho ligando x e y. Se n˜ao houver caminho conectando x e y, definimos dG(x, y) como infinito. Mostre que, para quaisquer trˆes v´ertices x, y e z vale dG(x, y) ≤ dG(x, z) + dG(z, y). 7. O complementar de um grafo G ´e o grafo G com os mesmos v´ertices de G e xy ´e uma aresta em G se, e somente se xy /∈ E(G). Mostre que se G n˜ao ´e conexo, ent˜ao G ´e conexo. 8. Mostre que em uma ´arvore, quais quer dois v´ertices s˜ao ligados por um ´unico caminho. 9. O diˆametro de um grafo ´e a maior distˆancia entre dois v´ertices no grafo. Mostre que se G tem diˆametro maior do trˆes, ent˜ao G tem diˆametro menor do que trˆes. 10. Um grafo G ´e dito bipartido completo quando V (G) = X1 ∪ X2, com X1 ∩ X2 = ∅ e se xy ´e uma aresta, ent˜ao x ∈ X1 e y ∈ X2. Quando |X1| = m e |X2| = n, escrevemos G = Km,n. A figura mostra o grafo K3,5. (a) Mostre que em um grafo bipartido completo com |X1| = m e |X2| = n, o n´umero de arestas ´e |E(G)| = mn. (b) Se G ´e um grafo bipartido completo com V (G) = X1 ∪ X2 e tal que d(x) = k, para todo x ∈ V (G), mostre que |X1| = |X2|. 11. Considere a seguinte rela¸c˜ao em N: S : x, y ∈ N ⇐⇒ x2 − y2 ´e par Mostre que S ´e uma rela¸c˜ao de equivalˆencia e determine as classes de equivalˆencia dessa rela¸c˜ao. 2 12. Mostre que quaisquer dois caminhos mais longos em um grafo conexo tˆem um v´ertice em comum. 13. Mostre que os dois grafos n˜ao s˜ao isomorfos. 3