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 é
Como cada vértice tem grau pelo menos 3, se houver
vértices, o mínimo que essa soma poderia ser é
.
Passo 3
Portanto, precisamos ter
que implica
Como
precisa ser inteiro, o maior valor possível é
.
Passo 4
Ainda precisamos checar se dá para usar exatamente
. Com 23 vértices, o grau mínimo somado seria
, 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