Seguem algumas provas de teoremas relacionados com a Teoria de Grafos. Veja, também, algumas estratégias de provas de teoremas.(Lógica Matemática)

 

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:

Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau ímpar. 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 ímpar. Suponha, agora, que n seja ímpar. Segue que o somatório dos graus dos vértices G é ímpar 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 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.