Teoremas de Grafos Conexos

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:

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'.

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 uma 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(v) ≥ (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.