Mostre que todo grafo com n vértices tem no máximo n(n-1) / 2 arestas.

Passo 1

Então, a gente tem um problema sobre grafos. A pergunta é: “Mostre que todo grafo com vértices tem no máximo arestas.” Isso está ligado ao conteúdo de teoria dos grafos, especificamente sobre quantas conexões (arestas) podem existir entre os vértices em um grafo simples (sem laços ou múltiplas arestas). Para resolver isso, vamos precisar entender como contar as possíveis conexões entre os vértices.

Passo 2

Primeiro, vamos pensar no que é um grafo simples. Um grafo simples é aquele onde não há laços (ou seja, uma aresta que conecta um vértice a ele mesmo) e não há múltiplas arestas entre os mesmos dois vértices. Então, cada aresta conecta exatamente dois vértices distintos.

Passo 3

Agora, vamos imaginar que temos vértices. A pergunta é: quantas arestas diferentes podemos formar conectando esses vértices sem repetir nenhuma conexão? Basicamente, queremos contar todas as combinações possíveis de pares de vértices.

Passo 4

Para contar essas combinações, usamos uma fórmula de combinação matemática. A combinação de C(n, 2) = n(n-1)2 elementos tomados de 2 em 2 é dada por:
Isso nos diz quantas maneiras diferentes podemos selecionar 2 vértices dentre os para formar uma aresta.

Passo 5

Então, representa exatamente o número máximo de arestas que um grafo simples com vértices pode ter. Isso ocorre quando cada par de vértices está conectado por uma aresta, ou seja, quando o grafo é completo.

Resposta

Portanto, todo grafo com vértices tem no máximo arestas.

Exercícios relacionados