Sabendo que cada vértice tem pelo menos grau 3 , qual o maior número possível de vértices em um grafo com 35 arestas? Lembre-se que a soma dos graus dos vértices é igual a duas vezes o número de arestas. Se cada aresta liga dois vértices teríamos 70 vértices de grau 1.

Passo 1

O enunciado pede o maior número de vértices em um grafo com 35 arestas, sabendo que cada vértice tem grau mínimo 3. O conteúdo aqui é o lema das mãos dadas (handshake lemma), que diz que a soma dos graus dos vértices é igual a duas vezes o número de arestas. Vamos usar isso para relacionar o número de vértices ao total de grau disponível entre eles.

Passo 2

Pelo lema das mãos dadas, temos que a soma dos graus de todos os vértices é
sumvin V d(v) ,=,2|E| ,=,2times35 ,=,70
Como cada vértice tem grau pelo menos 3, se houver n vértices, o mínimo que essa soma poderia ser é 3n.

Passo 3

Portanto, precisamos ter
3n <= 70
que implica
n <= 703 approx 23,33
Como n precisa ser inteiro, o maior valor possível é n=23.

Passo 4

Ainda precisamos checar se dá para usar exatamente n=23. Com 23 vértices, o grau mínimo somado seria 3times23=69, sobrando 1 unidade de grau a distribuir. Basta aumentar o grau de um vértice de 3 para 4, e assim a soma dos graus fica exatamente 70, respeitando todas as condições.

Resposta

23

Exercícios relacionados