Mostre que todo grafo
tem um vértice
tal que
e um vértice
tal que
. É verdade que todo grafo
tem um vértice
tal que
?
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
. 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
cujo grau é 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
com grau estritamente menor que a média, ou seja:
Para verificar isso, vamos considerar gráficos onde todos os vértices têm exatamente o grau médio. Por exemplo, no grafo completo
, 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.