Alguns Teoremas

Prévia do material em texto

13/11/2017 Alguns Teoremas
http://www.inf.ufsc.br/grafos/teo-prov/teoremas-de-grafos.htm 1/3
Alguns Teoremas
Seguem algumas provas de teoremas relacionados com a Teoria de Grafos. Veja, também, algumas estratégias de provas de teoremas.
Teorema 1)
Seja G(V,A) um grafo não orientado qualquer. Então , onde m é tamanho (número de areastas) de G .
Prova por indução estrutural:
Assuma que G(V,A) é um grafo não orientado qualquer, e seja P a propriedade , onde m é tamanho de G.
Base: Para G(1,0) tem-se que o grau do único vértice é zero e que m é zero. Logo, a propriedade é verdadeira.
Passo de indução: Seja G(V,A) um grafo com a propriedade P acima, e G' um grafo obtido a partir de G por uma das operações que se seguem:
1. inserção de vértice: O vértice inserido tem grau zero, pois não está conectado a nenhum outro vértice do grafo, de forma que a parcela à
esquerda da igualdade não é alterada. Como o número m de arestas não é modificado, a parcela à direita da igualdade também não é alterada. 
Logo a propriedade P é mantida em G'.
2. inserção de aresta: A aresta inserida conectada dois vértices de G' ou é um laço. No primeiro caso há o acréscimo de uma unidade no grau
de cada um dos dois vértices, enquanto que no segundo caso são acrescidas duas unidades no grau do vértice . Em ambos casos a parcela da
esquerda de P sofre um acréscimo de duas unidades. Como o número m de aresta aumenta em uma unidade, a parcela da direita de P sofre
um acréscimo de 2 unidades. Logo, a propriedade P é mantida.
Portanto, a propriedade P é verdadeira para qualquer grafo não orientado.
Teorema 2)
Seja G(V,A) um grafo não orientado qualquer. Então o número de vértices de grau ímpar de G é sempre par.
Prova direta:
13/11/2017 Alguns Teoremas
http://www.inf.ufsc.br/grafos/teo-prov/teoremas-de-grafos.htm 2/3
Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau impar. Como o somatório dos graus dos vértices G é par
(teorema 1), segue que n deve ser par. Logo, o número de vértices de grau ímpar de G é sempre par.
Prova por contradição:
Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau impar. Suponha, agora, que n seja impar. Segue que o
somatório dos graus dos vértices G é impar o que contradiz o teorema 1. Logo, o número de vértices de grau ímpar de G é sempre par.
Teorema 3)
Seja G(V,A) um grafo não orientado e conexo com n vértices. Então G contém pelo menos n-1 arestas.
Prova por indução estrutural:
Assuma que G(V,A) é um grafo não orientado e conexo com n vértices. Seja P a propriedade de que G tenha pelo menos n-1 arestas.
Base: G(1,0) tem um vértice e nenhuma aresta. Logo, a propriedade P é verdadeira.
Passo de indução: Seja G(V,A) um grafo não orientado e conexo com a propriedade P acima, e G' um grafo obtido a partir de G por uma das
operações que se seguem:
1. inserção de vértice: Para que o grafo G' permaneça conexo, ao se inserir um novo vértice em G' faz-se necessário inserir uma nova aresta
que o conecte a algum outro vértice de G'. Logo a propriedade P é mantida em G'.
2. inserção de aresta: A inserção de uma nova aresta não altera a propriedade P.
Portanto, G contém pelo menos n-1 arestas.
Teorema 4)
Seja G(V,A) um grafo não orientado e conexo com n vértices. Se G contém mais do que n-1 arestas, então G tem pelo menos um ciclo.
Prova direta:
Assuma que G(V,A) é um grafo não-orientado e conexo com n vértices e mais do que n-1 arestas. Segue que G contém um ou mais subgrafos
G'(V,A') com A' Ì A e |A'| = n-1, sendo que, como G é conexo, pelo menos um destes subgrafos é uma árvore. Seja T(V,A') esta árvore, a qual, por
13/11/2017 Alguns Teoremas
http://www.inf.ufsc.br/grafos/teo-prov/teoremas-de-grafos.htm 3/3
definição, não contém ciclos. Como G tem mais do que n-1 arestas, qualquer das arestas de A(G)-A(T) que for transposta de G para T criará uma
cadeia alternativa entre os dois vértices nos quais esta aresta incide. Logo G tem pelo menos um ciclo.
Teorema 5)
Seja G(V,A) um grafo não orientado de ordem p ≥ 2, sendo que grau(v) ≥ ( p-1)/2 para todo v ∈ V. Então G é conexo.
Prova por contradição:
Seja G(V,A) um grafo não orientado de ordem p ≥ 2, sendo que grau ≥ (p-1)/2, para todo v ∈ V. Suponha que G não seja conexo. Segue que G
possui pelo menos 2 componentes conexas. Sejam G1,G2, ... Gm as m componentes e sejam p1, p2, ... pm suas respectivas ordens. Tome, agora, um
xi ∈ V(Gi), o qual tem grau(xi) ≥ (p-1)/2 (em função do enunciado do teorema). Segue que pi ≥ ((p-1)/2)+1 (os vértices adjacentes a xi mais o
próprio xi), ou seja, pi ≥ (p+1)/2, e que p1+p2+...+pm ≥ m(p+1)/2. Mas como p1+ p2+...+pm = p, segue que p ≥ m(p+1)/2 o que é uma contradição já
que m ≥ 2. Logo, G é conexo.