Lista 1: Conceitos Básicos em Grafos

Teoria dos Grafos Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Lista 1 Conceitos básicos em grafos 1 Prove o teorema do aperto de mãos fazendo indução no número de vértices 2 Seja G um grafo conexo com pelo menos dois vértices e seja u V G um vértice tal que du 1 Mostre que G u é conexo 3 Seja G um grafo com V G 4 Prove que se EG V G1 então G possui um vértice com grau pelo menos 3 4 Mostre que todo grafo conexo com pelo menos dois vértices e que não contém ciclos tem pelo menos dois vértices de grau 1 5 Mostre que δG 2EG V G G 6 O complemento G de um grafo G é o grafo cujo conjunto de vértices é igual a V G e cujas arestas são os pares de vértices não adjacentes de G Prove que G ou G é conexo 7 Prove que quaisquer dois caminhos mais longos em um grafo conexo possuem um vértice em comum 8 Prove que todo passeio fechado de comprimento ímpar contém um ciclo ímpar 9 A cintura de um grafo G denotada por gG é o menor comprimento de um ciclo em G Caso G não possua um ciclo então definimos gG Seja G um grafo com gG 5 Mostre que G tem pelo menos δG2 1 vértices 10 Prove ou dê um contraexemplo se uv EG é aresta de corte então u e v são vértices de corte 11 Prove ou mostre um contraexemplo se todo vértice de um grafo conexo G tem grau 2 então G é um ciclo 12 Há um certo número de homens e 15 mulheres em um salão Cada homem cumpri mentou exatamente 6 mulheres e cada mulher cumprimentou exatamente 8 homens Há quantos homens no salão 13 Prove que todo caminho é bipartido 14 Seja G um grafo X Y bipartido e sejam u v V G Prove que um uvcaminho tem comprimento par se e somente se u e v estão na mesma parte da bipartição isto é u v X ou u v Y 15 Prove que toda árvore é bipartida 1 16 Seja G um grafo e f uma aresta de G Prove que se f não pertence a um ciclo então f é de corte 17 Se G é um grafo conexo com n vértices e n 1 arestas então G não tem ciclos 18 Se G é um grafo conexo com n vértices e G não tem ciclos então G tem n 1 arestas 19 Prove que se G é uma árvore então existe um único caminho entre qualquer par de vértices de G 20 Prove que toda árvore com grau máximo G 2 tem pelo menos G folhas Mostre que isso é o melhor possível construindo uma árvore de ordem n com exa tamente G folhas para cada escolha de n e G com n G 2 21 Prove que toda árvore com ao menos dois vértices possui ao menos duas folhas 22 Se T é uma árvore prove que um vértice v V T é de corte se e somente se ele não é uma folha 23 Seja G um grafo conexo Prove que G é uma árvore se e somente se EG V G 1 2