Mostre que todo grafo G tem um vértice v tal que g(v) <= 2|A(G)| /|V(G)| e um vértice w tal que g(w) >= 2|A(G)| /|V(G)|. É verdade que todo grafo G tem um vértice x tal que g(x)<2|A(G)| /|V(G)| ?

Passo 1

Primeiro, vamos resumir o que a questão está pedindo. Temos um grafo com um conjunto de arcos e um conjunto de vértices . A função representa o grau do vértice , ou seja, quantos arcos estão ligados a ele. A questão quer que a gente mostre que existe pelo menos um vértice com grau menor ou igual a e outro com grau maior ou igual a . Além disso, pergunta se sempre existe um vértice com grau estritamente menor que .
Vamos precisar usar o conceito de grau médio de um grafo, que é calculado como . Isso porque cada arco contribui para o grau de dois vértices.

Passo 2

Vamos calcular o grau médio do grafo g = 2|A(G)||V(G)| . O grau médio é dado por:
Isso vem do fato de que cada arco conecta dois vértices, então somando os graus de todos os vértices, a gente conta cada arco duas vezes.

Passo 3

Agora, vamos usar a propriedade que em qualquer conjunto de números, pelo menos um número é menor ou igual à média, e pelo menos um é maior ou igual à média. Aplicando isso aos graus dos vértices do grafo:
  • Existe pelo menos um vértice g(v) <= 2|A(G)||V(G)| cujo grau g(w) >= 2|A(G)||V(G)| é menor ou igual ao grau médio :
  • Da mesma forma, existe pelo menos um vértice cujo grau é maior ou igual ao grau médio :
Isso garante que sempre teremos vértices tanto abaixo quanto acima ou igual ao grau médio.

Passo 4

Agora, vamos analisar se sempre existe um vértice g(x) < 2|A(G)||V(G)| com grau estritamente menor que a média, ou seja:
g(x) = n - 1
Para verificar isso, vamos considerar gráficos onde todos os vértices têm exatamente o grau médio. Por exemplo, no grafo completo g = 2 cdot n(n-1)2n = n - 1 , onde cada vértice está conectado a todos os outros vértices. Aqui, o grau de cada vértice é:
E o grau médio é:
Então, todos os vértices têm grau igual à média, não existindo nenhum com grau estritamente menor que a média. Portanto, nem todo grafo garante a existência de um vértice com .

Resposta

Não, nem todo grafo possui um vértice com grau . Por exemplo, nos grafos completos, todos os vértices têm grau igual ao grau médio, e nenhum tem grau estritamente menor que a média.

Exercícios relacionados