Uma das noções mais simples e ao mesmo tempo mais úteis em teoria dos grafos é o grau de um vértice — quantas arestas estão conectadas a ele. A partir dessa definição aparentemente trivial, emerge um dos resultados mais elegantes da área: o Teorema do Aperto de Mãos.
Por que Grau de um Vértice Importa? #
O grau de um vértice é uma medida local extremamente simples, mas que aparece por trás de resultados importantes em matemática e computação:
- Redes sociais: o grau de um vértice mede diretamente o número de conexões de uma pessoa (ou perfil) — a base de métricas de centralidade e de detecção de “hubs” em uma rede.
- Roteamento e infraestrutura: em uma rede de computadores ou de transporte, o grau de um nó indica quantas rotas alternativas passam por ele, algo essencial para análise de robustez e de pontos únicos de falha.
- Design de circuitos e hardware: o grau de um vértice em um grafo de conexões limita o número de portas ou pinos físicos necessários naquele ponto do circuito.
- Verificação de estruturas: como veremos no Teorema do Aperto de Mãos, a soma dos graus de um grafo é sempre igual ao dobro do número de arestas — uma verificação rápida e barata da consistência de qualquer estrutura de grafo antes de rodar algoritmos mais custosos sobre ela.
Grau de um Vértice #
Seja \(G = (V, E)\) um grafo e \(v \in V\). O grau de \(v\), denotado \(d(v)\) ou \(d_G(v)\) (quando há mais de um grafo em jogo), é o número de arestas incidentes em \(v\) — em outras palavras, o número de vértices adjacentes a \(v\):
$$d(v) = |N(v)| = |\{w \in V \mid (v, w) \in E\}|$$Em multigrafos com laços (arestas de um vértice para ele mesmo), a convenção usual é que um laço contribui com 2 para o grau do vértice — pois o laço é incidente duas vezes no vértice.
Exemplo 1
Enunciado: Seja \(G = (V, E)\) com
$$V = \{x,\ y,\ z,\ v,\ w,\ t,\ u\}$$$$E = \{(x,y),\ (y,z),\ (x,z),\ (x,w),\ (x,v),\ (z,v),\ (w,v),\ (z,t)\}$$
Calcule o grau de cada vértice de \(G\).
Solução: Contando as arestas incidentes em cada vértice:
- \(d(x) = 4\) (vizinhos \(y, z, w, v\))
- \(d(y) = 2\) (vizinhos \(x, z\))
- \(d(z) = 4\) (vizinhos \(y, x, v, t\))
- \(d(v) = 3\) (vizinhos \(x, z, w\))
- \(d(w) = 2\) (vizinhos \(x, v\))
- \(d(t) = 1\) (vizinho \(z\))
- \(d(u) = 0\) (nenhum vizinho — vértice isolado)
A figura abaixo mostra \(G\) com o grau de cada vértice anotado. Este é o grafo que reaproveitaremos nos próximos exemplos.
Exemplo 2
Enunciado: Seja \(G\) o multigrafo com \(V = \{x, y, z, v, w\}\), no qual há um laço no vértice \(z\), duas arestas paralelas entre \(x\) e \(y\) e três entre \(w\) e \(v\) (veja a figura):
$$E = \{(x,y),\ (x,y),\ (y,z),\ (y,v),\ (x,v),\ (x,w),\ (z,v),\ (w,v),\ (w,v),\ (w,v),\ (z,z)\}$$Calcule o grau de cada vértice, lembrando que o laço em \(z\) contribui com 2 unidades.
Solução:
- \(d(x) = 4\)
- \(d(y) = 4\)
- \(d(z) = 4\) (inclui as 2 unidades do laço)
- \(d(v) = 6\)
- \(d(w) = 4\)
A figura a seguir mostra o multigrafo com as arestas paralelas (em laranja) e o laço em \(z\) destacados.
Grau Mínimo e Grau Máximo #
Para um grafo \(G\):
- \(\delta(G)\) = grau mínimo = menor grau entre todos os vértices de \(G\)
- \(\Delta(G)\) = grau máximo = maior grau entre todos os vértices de \(G\)
Exemplo 3
Enunciado: Considere novamente o grafo \(G\) do Exemplo 1. Determine \(\delta(G)\) e \(\Delta(G)\).
Solução: Os graus calculados no Exemplo 1 foram \(d(x)=4\), \(d(y)=2\), \(d(z)=4\), \(d(v)=3\), \(d(w)=2\), \(d(t)=1\), \(d(u)=0\). O menor valor é \(0\) (vértice \(u\)) e o maior é \(4\) (vértices \(x\) e \(z\)). Portanto:
$$\delta(G) = 0 \qquad \Delta(G) = 4$$O grafo \(G\), com \(u\) (grau mínimo) e \(x\), \(z\) (grau máximo) identificáveis pelas anotações de grau.
Grafos Regulares #
Alguns grafos têm todos os vértices com o mesmo grau — são os grafos regulares.
Um grafo \(G\) é dito regular se todos os seus vértices têm o mesmo grau. Em particular, se \(d(v) = k\) para todo \(v \in V(G)\), dizemos que \(G\) é \(k\)-regular ou regular de grau \(k\).
Exemplo 4
Enunciado: Classifique os grafos abaixo quanto à regularidade.
- \(G_1\): três vértices isolados \(a, b, c\)
- \(G_2\): dois pares de vértices ligados por uma aresta cada, \((x,y)\) e \((z,w)\)
- \(G_3\): um ciclo de 4 vértices \(1\text{-}2\text{-}3\text{-}4\text{-}1\)
Solução:
- \(d(a) = d(b) = d(c) = 0\) → \(G_1\) é 0-regular
- \(d(x) = d(y) = d(z) = d(w) = 1\) → \(G_2\) é 1-regular
- \(d(1) = d(2) = d(3) = d(4) = 2\) → \(G_3\) é 2-regular
Os três grafos são mostrados lado a lado a seguir.
Exemplo 4 (continuação)
Enunciado: Classifique também os grafos \(G_4\) (grafo do cubo, com 8 vértices), \(G_5 = K_4\) e \(G_6 = K_5\).
Solução:
- \(G_4\) (cubo): todo vértice tem grau \(3\) → 3-regular
- \(G_5 = K_4\): todo vértice tem grau \(3\) → 3-regular
- \(G_6 = K_5\): todo vértice tem grau \(4\) → 4-regular
Os três grafos são mostrados a seguir: o cubo \(G_4\), \(K_4\) e \(K_5\).
Em geral, \(K_n\) é regular de grau \(n-1\): cada vértice é adjacente a todos os outros \(n-1\) vértices do grafo.
Soma dos Graus de um Grafo #
Antes de enunciar o resultado geral, vale a pena somar os graus de dois grafos concretos e observar o padrão que surge.
Exemplo 5
Enunciado: Some os graus de todos os vértices do grafo \(G\) do Exemplo 1.
Solução:
$$\sum_{v \in V} d(v) = d(x)+d(y)+d(z)+d(v)+d(w)+d(t)+d(u) = 4+2+4+3+2+1+0 = 16$$O grafo \(G\) tem exatamente \(8\) arestas, e \(16 = 2 \times 8\): a soma dos graus é exatamente o dobro do número de arestas.
Exemplo 6
Enunciado: Some os graus de todos os vértices do grafo do cubo \(G_4\) (Exemplo 4), que tem 8 vértices, todos de grau 3.
Solução:
$$\sum_{v \in V(G_4)} d(v) = 3 \times 8 = 24$$O grafo \(G_4\) tem exatamente \(12\) arestas, e novamente \(24 = 2 \times 12\).
Os dois exemplos acima sugerem um padrão geral, que formalizamos a seguir.
O Teorema do Aperto de Mãos #
O resultado a seguir é um dos mais elegantes da teoria dos grafos. O nome vem de uma analogia: se \(n\) pessoas estão em uma sala e cada par de pessoas pode ou não apertar as mãos, a soma do número de apertos de cada pessoa é necessariamente igual ao dobro do número total de apertos (pois cada aperto é contado duas vezes — uma para cada pessoa envolvida).
Para qualquer grafo \(G = (V, E)\):
$$\sum_{v \in V} d(v) = 2|E|$$Prova:
Cada aresta \((u, v) \in E\) contribui exatamente 1 para \(d(u)\) e exatamente 1 para \(d(v)\). Logo, cada aresta é contada exatamente 2 vezes na soma \(\sum_{v \in V} d(v)\). Portanto, \(\sum_{v \in V} d(v) = 2|E|\), que é o que queríamos demonstrar. \(\blacksquare\)
O Teorema do Aperto de Mãos vale também para multigrafos (usando a convenção de que cada laço contribui com 2 unidades para o grau do vértice).
Na prática: o Teorema do Aperto de Mãos em uma rede social real
Entre 1970 e 1972, o antropólogo Wayne W. Zachary observou as interações sociais dos 34 membros de um clube universitário de caratê e registrou, vértice a vértice, quem interagia com quem fora das aulas. Esse conjunto de dados ficou conhecido como o Karate Club de Zachary e se tornou um dos grafos mais estudados em análise de redes sociais.
Durante o estudo, um conflito entre o instrutor de caratê (apelidado de
“Mr. Hi”) e o administrador do clube (“John A.”) levou à divisão do grupo:
metade dos membros formou um novo clube em torno de Mr. Hi, e o restante
ficou com outro instrutor ou abandonou o caratê. O mais notável é que
Zachary conseguiu prever a divisão usando só a estrutura do grafo — um
algoritmo de fluxo máximo aplicado à rede de interações acertou o destino
de 33 dos 34 membros, errando apenas um (o membro 9 na numeração de Zachary,
que vai de 1 a 34 — no networkx, que numera a partir de 0, é o vértice 8 —,
cuja escolha real destoou do que a estrutura da rede sugeria).
O networkx já traz esse grafo pronto, o que permite verificar o Teorema
do Aperto de Mãos em uma rede real (não só em exemplos de 7 ou 8 vértices)
e usar o grau para encontrar os membros mais influentes:
import networkx as nx
G = nx.karate_club_graph()
degrees = dict(G.degree())
soma_graus = sum(degrees.values())
arestas = G.number_of_edges()
print(f"Soma dos graus: {soma_graus}")
print(f"2 x |E|: {2 * arestas}")
print(f"Teorema verificado: {soma_graus == 2 * arestas}")
grau_max = max(degrees.values())
hubs = [v for v, d in degrees.items() if d == grau_max]
print(f"Vértice(s) de maior grau: {hubs} (grau {grau_max})")Soma dos graus: 156
2 x |E|: 156
Teorema verificado: True
Vértice(s) de maior grau: [33] (grau 17)O teorema se confirma mesmo em uma rede com 34 vértices e 78 arestas. E o
resultado do grau máximo não é coincidência: o vértice 33 é exatamente o
administrador do clube (club: "Officer"), e o segundo colocado, o
vértice 0 com grau 16, é o instrutor (club: "Mr. Hi") — os dois
polos ao redor dos quais o grupo se dividiu. O grau, uma medida puramente
local e fácil de calcular, já aponta para os dois personagens mais centrais
da rede.
A figura abaixo mostra o grafo completo, colorido pelas duas facções que
resultaram da cisão, com os dois hubs (vértices 0 e 33) destacados por
um contorno preto.
Corolários #
Corolário 1: A soma dos graus de todos os vértices de qualquer grafo é sempre um número par.
Prova: Pelo Teorema do Aperto de Mãos, \(\sum_{v \in V} d(v) = 2|E|\), que é par por definição (múltiplo de 2). Portanto, a soma dos graus de qualquer grafo é sempre par, que é o que queríamos demonstrar. \(\blacksquare\)
Corolário 2: Em qualquer grafo, o número de vértices com grau ímpar é sempre par.
Prova: Separe os vértices em dois grupos: \(V_{par}\) (grau par) e \(V_{ímpar}\) (grau ímpar). Então:
$$\sum_{v \in V_{par}} d(v) + \sum_{v \in V_{ímpar}} d(v) = 2|E|$$O primeiro somatório é par (soma de parcelas pares). Como o total \(2|E|\) também é par, o segundo somatório — soma dos graus ímpares — também deve ser par. Mas uma soma de números ímpares só é par quando há uma quantidade par deles. Portanto, o número de vértices de grau ímpar em qualquer grafo é sempre par, que é o que queríamos demonstrar. \(\blacksquare\)
Corolário 3: Em um grafo \(k\)-regular com \(n\) vértices:
$$|E| = \frac{nk}{2}$$Prova: Seja \(G\) um grafo \(k\)-regular com \(n\) vértices e \(m = |E|\). Pelo Teorema do Aperto de Mãos:
$$\underbrace{k + k + \cdots + k}_{n \text{ parcelas}} = \sum_{v \in V} d(v) = 2m$$Logo \(nk = 2m\), ou seja, \(m = \dfrac{nk}{2}\). Portanto, todo grafo \(k\)-regular com \(n\) vértices tem exatamente \(\dfrac{nk}{2}\) arestas, que é o que queríamos demonstrar. \(\blacksquare\)
Para que um grafo \(k\)-regular com \(n\) vértices exista, \(nk\) deve ser par. Em particular:
- Se \(k\) é par, qualquer \(n\) funciona
- Se \(k\) é ímpar, \(n\) deve ser par
Aplicando o Corolário 3
Pergunta: Existe um grafo 3-regular com 7 vértices?
Se existisse, teria \(|E| = 7 \times 3 / 2 = 10{,}5\) arestas — impossível! Portanto, não existe grafo 3-regular com 7 vértices.
Sequência de Graus #
A sequência de graus de um grafo \(G\) com \(n\) vértices é a lista dos graus de todos os vértices, em ordem crescente (permitindo repetições quando necessário):
$$(d_1, d_2, \ldots, d_n) \quad \text{com } d_1 \leq d_2 \leq \cdots \leq d_n$$
Exemplo 7
Enunciado: Determine a sequência de graus do grafo \(G\) do Exemplo 1.
Solução: Os graus calculados foram \(d(u)=0\), \(d(t)=1\), \(d(y)=2\), \(d(w)=2\), \(d(v)=3\), \(d(x)=4\), \(d(z)=4\). Ordenando de forma crescente:
$$(0,\ 1,\ 2,\ 2,\ 3,\ 4,\ 4)$$
Exemplo 8
Enunciado: Determine a sequência de graus do grafo do cubo \(G_4\).
Solução: Todos os 8 vértices têm grau 3, logo a sequência de graus é:
$$(3,\ 3,\ 3,\ 3,\ 3,\ 3,\ 3,\ 3)$$
Exercícios #
Os exercícios a seguir aplicam o Teorema do Aperto de Mãos e seus corolários em contextos diferentes.
Exercício 1: Número de vértices de grau ímpar
Enunciado: Em uma festa com 30 pessoas, cada pessoa apertou a mão de um número específico de outras pessoas. Prove que o número de pessoas que apertaram a mão um número ímpar de vezes é par.
Solução: Modele a festa como um grafo: pessoas são vértices, apertos de mão são arestas. Pelo Corolário 2 do Teorema do Aperto de Mãos, o número de vértices com grau ímpar é sempre par. Portanto, o número de pessoas que apertaram mãos um número ímpar de vezes é par, que é o que queríamos demonstrar. \(\blacksquare\)
Exercício 2: Princípio da gaveta para graus
Enunciado: Prove que em qualquer grafo simples com \(n \geq 2\) vértices, existem pelo menos dois vértices com o mesmo grau.
Solução: Os possíveis graus em um grafo simples com \(n\) vértices são \(0, 1, 2, \ldots, n-1\) — ou seja, \(n\) valores possíveis para \(n\) vértices. No entanto, os valores \(0\) e \(n-1\) não podem ocorrer simultaneamente: um vértice isolado (grau \(0\)) não pode coexistir com um vértice universal (grau \(n-1\)), pois o vértice universal seria adjacente ao isolado — uma contradição. Logo, há no máximo \(n-1\) valores distintos de grau disponíveis para \(n\) vértices. Pelo princípio da casa dos pombos (ou princípio da gaveta), pelo menos dois vértices devem compartilhar o mesmo grau. Portanto, todo grafo simples com \(n \geq 2\) vértices tem dois vértices de mesmo grau, que é o que queríamos demonstrar. \(\blacksquare\)
Resumo #
A tabela a seguir resume os principais conceitos e resultados apresentados neste artigo.
| Conceito | Notação | Descrição |
|---|---|---|
| Grau de \(v\) | \(d(v)\), \(d_G(v)\) | Número de arestas incidentes em \(v\) |
| Grau mínimo | \(\delta(G)\) | Menor grau no grafo |
| Grau máximo | \(\Delta(G)\) | Maior grau no grafo |
| Grafo \(k\)-regular | — | Todo vértice tem grau \(k\) |
| Teorema do Aperto de Mãos | \(\sum d(v) = 2|E|\) | Soma dos graus = dobro das arestas |
| Corolário 1 | — | Soma dos graus de qualquer grafo é par |
| Corolário 2 | — | Número de vértices de grau ímpar é par |
| Corolário 3 | \(|E| = \dfrac{nk}{2}\) | Arestas de um grafo \(k\)-regular com \(n\) vértices |
| Sequência de graus | \((d_1, \ldots, d_n)\) | Graus listados em ordem crescente |
Próximos Passos #
O grau de cada vértice e a sequência de graus de um grafo são ferramentas úteis, mas têm um limite claro: dois grafos podem ter exatamente a mesma sequência de graus e, ainda assim, ser estruturas completamente diferentes — ou, ao contrário, parecer diferentes só porque seus vértices foram rotulados de forma diferente, quando na verdade têm a mesma estrutura. Faltam ferramentas para responder à pergunta “esses dois grafos são, essencialmente, o mesmo grafo?”. Essa é a pergunta que motiva o isomorfismo de grafos, tema do próximo artigo da série, onde também veremos como representar grafos por matrizes de adjacência e de incidência.
