Seja o complemento de um grafo . Calcule e em função de e de .
Passo 1
Aqui temos um exercício sobre grafos e seus complementos. Precisamos calcular o grau mínimo () e o grau máximo (De) do complemento de um grafo G, usando o grau mínimo (de) e o grau máximo (De) do próprio grafo G. Para resolver isso, vamos lembrar que o complemento de um grafo conecta exatamente os pares de vértices que não estão conectados no grafo original.
Passo 2
Primeiro, vamos relembrar o que é o complemento de um grafo. Dado um grafo G com n vértices, o complemento de G, denotado por G, é um grafo onde dois vértices estão conectados se e somente se eles não estão conectados em G.
Passo 3
Sabemos que em um grafo com n vértices, cada vértice pode ter no máximo n-1 conexões (grau máximo). Portanto, se um vértice tem grau d em G, seu grau no complemento G será n-1 - d.
Passo 4
Para encontrar o grau mínimo do complemento, de, consideramos o grau máximo do grafo original, De. Assim,
de
Passo 5
Similarmente, para o grau máximo do complemento, De, consideramos o grau mínimo do grafo original, de. Logo,