Prova: todo grafo completo é conexo

Como vimos antoriormente (“Uma introdução à teoria dos grafos – Parte 1” e “Grafos – Algoritmo do Caminho Mínimo“), Grafos são estruturas muito interessantes para resolução de problemas, pois muitos destes podem ser reduzidos a um problema de grafos – como abordado no artigo “O uso da abstração para a resolução de problemas – Redutibilidade“.

Entretanto, os grafos, como estrutura, podem ser estudados teoricamente como um assunto próprio, separado de todos os demais. E esta é a proposta deste artigo.

Vamos começar com uma deinição simples: um grafo G é dito conexo se existe um caminho entre dois vértices u e v quaisquer. Em outras palavras, um grafo é conexo se não existe nenhum vértice com grau menor que um.

Agora, vamos partir para a diversão matemática. Primeiro, vamos provar, usando a técnica de contradição, que todo grafo completo é conexo.

As provas por contradição, apesar de não serem vistas com bons olhos por muitos matemáticos, são muito divertidas de se fazer e uma das minhas técnicas favoritas. Bom, mãos a obra:

Prova por contradição:

Suponha que exista um grafo G completo que seja desconexo.

Como G é completo, sabemos que possui pelo menos um vértice v com d(v) = n – 1. Sendo assim, não pode existir um outro vértice v com d(v) < 1, o que é uma contradição.

Fácil não? Vamos agora partir pra uma um pouco mais desafiadora: Mostrar que todo caminho é um
grafo conexo. Mais uma vez irei uma prova por contradição.

Suponha que existe um caminho C desconexo. Sejam v0 e vi os vértices nas extremidades de C. Como C é desconexo, então, partindo de v0 deve existir uma trilha que chega até um vértice u, onde d(u) = 0 e, partindo de u, chega até vi. Isto é um absurdo, pois um vértice u com d(u) = 0 não pode fazer parte de nenhum caminho.

Tão fácil quanto a outra, certo? A prova acima também pode ser aplicada para ciclos, bastaria que v0 = vi.

Agora, fica aqui o desafio: como transformar estas provas em um algoritmo eficiente para determinar se um grafo é conexo ou desconexo? (Não vale apelar para a força bruta, não é eficiente!).