Teoremas e Lemas sobre Grafos e Caminhos

e y vk Se todos os vértices de W são distintos então W é um caminho e não há nada a provar Então suponha que existe ao menos um vértice que se repete em W Seja vi o vértice com menor valor i que se repete em W e seja vj sua primeira repetição portanto i j Construa Q v0 vi vj1 vk a partir de W Note que Q é um xypasseio de comprimento menor do que k Portanto por hipótese vale que Q contém um xy caminho P v0 u1 u2 ut vk Como Q está contido em W P também está contido em W e o resultado segue Teorema 24 Se G é um grafo com δG 2 então G contém um caminho de comprimento pelo menos δG e um ciclo de comprimento pelo menos δG 1 Demonstração Seja P v0 v1 vk um caminho maximal em G Note que todo vizinho de vk está em P Como dvk δG vk tem pelo menos δG vizinhos e assim P tem comprimento pelo menos δG Seja i o menor índice tal que vivk EG O ciclo C vi vi1 vk vi tem pelo menos δG1 arestas pois contém vk e todos os seus vizinhos Lema 25 Todo grafo que não contém ciclos tem pelo menos dois vértices de grau 1 A cintura de um grafo G denotada gG é a quantidade de arestas do menor ciclo de G ciclo mínimo ou se G não tem ciclos g de girth Teorema 26 Se G é um grafo kregular com gG 4 então G tem pelo menos 2k vértices Demonstração Seja G um grafo kregular com gG 4 Considere v V G qualquer Note que Nv dv k Como G não tem triângulos então não existem arestas em GNv Assim um vértice u Nv tem como vizinhos v e outros k1 vértices fora de Nv Então V G 1NvNu1 2k Teorema 27 Seja G um grafo no qual todos os vértices têm grau pelo menos 2 Então G contém um ciclo Demonstração Seja P v0 v1 vk1 vk um caminho mais longo em G Como o grau de vk é pelo menos 2 ele tem algum vizinho v diferente de vk1 Se v não estiver em P então P poderia ser aumentado uma contradição Então v vi para algum i 0 i k 2 e vi vi1 vk vi é um ciclo em G 11