Euler, Hamilton, planaridade e coloração

Num grafo, percorrer todas as arestas e visitar todos os vértices são problemas diferentes. Um grafo pode permitir o primeiro e impedir o segundo, como a borboleta abaixo. Antes de aplicar um critério, identifica o que tem de ser visitado e o que pode repetir-se.

Trilhos e circuitos de Euler

Um trilho de Euler usa todas as arestas exatamente uma vez. Um circuito de Euler é um desses trilhos que termina onde começou. Os vértices podem repetir-se.

Para um grafo não dirigido com arestas, precisamos de que todos os vértices incidentes em arestas estejam na mesma componente. Sob essa condição:

• Existe um circuito de Euler se e só se todos os graus são pares.
• Existe um trilho de Euler se e só se há zero ou dois vértices de grau ímpar.
• Se há exatamente dois ímpares, o trilho começa num deles e acaba no outro.

A formulação habitual da cadeira assume o grafo conexo. Excluir vértices isolados da condição permite tratar o mesmo critério quando eles estão presentes. Um grafo sem arestas admite o percurso sem passos a partir de qualquer vértice que exista.

A necessidade da paridade vem de cada visita intermédia usar uma aresta para entrar e outra para sair. Num circuito, o início também emparelha a primeira saída com a última entrada. Num trilho aberto, sobram os dois extremos.

Para construir um circuito num grafo com graus pares, começa um trilho sem repetir arestas. Não fica preso num vértice diferente do inicial, pois cada entrada deixa uma saída disponível. Se ainda sobram arestas, a conectividade garante um vértice do circuito ligado a arestas não usadas. Constrói outro circuito a partir dele e intercala-o no primeiro. Repetindo, usas todas as arestas.

Caminhos e ciclos de Hamilton

Um caminho de Hamilton visita todos os vértices exatamente uma vez. Um ciclo de Hamilton faz isso e fecha-se na origem. Não precisa de usar todas as arestas.

Não há um critério de paridade semelhante ao de Euler. Para provar existência, apresenta a sequência completa de vértices e verifica cada ligação. Para provar impossibilidade, usa uma obstrução necessária:

• Um vértice de grau 1 impede um ciclo de Hamilton.
• Um grafo desconexo não tem caminho de Hamilton que visite todos os vértices.
• Se retirar um vértice separa o grafo em várias componentes, não há ciclo de Hamilton. O ciclo sem esse vértice teria de ser um caminho que ainda liga todos os restantes.

Estas condições não são critérios suficientes. Ter todos os graus pelo menos 2 não garante um ciclo de Hamilton.

O exemplo da borboleta

Os graus são $2,2,4,2,2$. Há um circuito de Euler:

$$a,b,c,d,e,c,a.$$

Usa as seis arestas uma vez e repete apenas o vértice $c$ durante o percurso. Não há ciclo de Hamilton. Retirar $c$ deixa as duas componentes $\{a,b\}$ e $\{d,e\}$; um ciclo teria de voltar a passar por $c$ para as ligar.

O circuito resulta da intercalação: no primeiro triângulo, $a,b,c,a$, paramos ao chegar a $c$; percorremos $c,d,e,c$ no segundo e retomamos a aresta $c,a$. As arestas dos dois circuitos são disjuntas, por isso a intercalação não repete nenhuma.

Há, no entanto, um caminho de Hamilton: $a,b,c,d,e$. O triângulo também mostra que o grafo não é bipartido.

Grafos bipartidos

Um grafo é bipartido quando os vértices podem dividir-se em duas partes disjuntas, de forma a que todas as arestas liguem partes diferentes. Isto equivale a poder colorir os vértices com duas cores sem ligar vértices da mesma cor. Admitimos uma parte vazia para grafos sem arestas.

Um grafo é bipartido se e só se não tem ciclos de comprimento ímpar. Se alternarmos as partes ao longo de um ciclo, só voltamos à parte inicial depois de um número par de passos. Na direção inversa, podemos colorir por paridade da distância a uma origem em cada componente; uma aresta entre cores iguais permitiria construir um ciclo ímpar.

Todo o ciclo par é bipartido. Todo o ciclo ímpar precisa de uma terceira cor. Todas as árvores são bipartidas, pois não têm ciclos.

Se um grafo bipartido tem ciclo de Hamilton, as duas partes têm o mesmo tamanho. O ciclo alterna entre elas e visita todos os vértices. Esta condição não garante a existência do ciclo.

Para $K_{m,n}$ com $m,n\ge1$, há $mn$ arestas. Num grafo bipartido simples com $v$ vértices, o máximo é $\lfloor v^2/4\rfloor$: o produto dos tamanhos das duas partes é maior quando são tão próximos quanto possível. Assim, cinco vértices e sete arestas já excluem bipartição, pois o máximo seria $2\cdot3=6$.

Planaridade e fórmula de Euler

Um grafo é planar quando pode desenhar-se no plano sem cruzamentos entre arestas, exceto nos extremos comuns. Ter cruzamentos num desenho não prova que seja não planar, porque pode existir outro desenho.

Desenho com cruzamento

Desenho sem cruzamentos

Uma representação planar divide o plano em faces, incluindo a face exterior. Para um grafo finito, conexo e planar:

$$v-e+f=2.$$

Aqui, $v=|V|$, $e=|E|$ e $f$ é o número de faces dessa representação. Uma árvore tem uma única face, logo $n-(n-1)+1=2$.

Podemos justificar a fórmula retirando arestas de ciclos. Cada remoção conserva a conectividade, diminui $e$ em 1 e junta duas faces, diminuindo $f$ em 1. Ao chegar a uma árvore, a expressão vale 2 e não mudou pelo caminho.

Com $c$ componentes não vazias, a fórmula generaliza-se para $v-e+f=1+c$. Não uses a versão conexa sem conferir a hipótese.

Limites de arestas

Para um grafo simples planar com $v\ge3$:

$$e\le3v-6.$$

Se não há triângulos, em particular se o grafo é bipartido:

$$e\le2v-4.$$

Num grafo conexo que contém um ciclo, o limite de cada face percorre pelo menos três arestas, ou quatro se não há triângulos. Cada aresta conta duas vezes nos limites das faces; uma ponte conta duas vezes na mesma face. Logo $3f\le2e$ ou $4f\le2e$. Como $f=2-v+e$, a primeira dá $3(2-v+e)\le2e$, isto é, $e\le3v-6$. A segunda dá $e\le2v-4$.

Se o grafo conexo não tem ciclos, é uma árvore: $e=v-1\le2v-4\le3v-6$ para $v\ge3$. Num grafo desconexo, podemos ligar as componentes por pontes sem criar triângulos ou cruzamentos. O grafo conexo obtido satisfaz os limites e tem mais arestas do que o original. Não apliques o argumento “quatro lados por face” diretamente a uma árvore.

$K_5$ tem cinco vértices e dez arestas, mas $3v-6=9$, por isso não é planar. $K_{3,3}$ tem seis vértices e nove arestas; como é bipartido, o limite seria $2v-4=8$, por isso também não é planar.

Satisfazer uma desigualdade necessária não prova planaridade. Para provar que um grafo é planar, podes fornecer uma representação sem cruzamentos. Para $K_4$, desenha um triângulo exterior e o quarto vértice dentro, ligado aos três.

Coloração e número cromático

Uma $k$-coloração atribui a cada vértice uma das $k$ cores, com cores diferentes em extremos de cada aresta. O número cromático $\chi(G)$ é o menor $k$ possível. Para determinar esse mínimo, precisamos de duas direções: uma coloração que mostra que $k$ cores chegam e uma razão por que menos não chegam.

• $\chi(K_n)=n$, porque todos os pares são adjacentes.
• $\chi(C_n)=2$ se $n$ é par e $3$ se é ímpar.
• $\chi(K_{m,n})=2$ se ambas as partes são não vazias.
• Um grafo não vazio sem arestas tem número cromático 1.

Na borboleta, um triângulo exige pelo menos três cores. Três chegam: dá uma cor a $c$, outra a $a,d$ e outra a $b,e$. Portanto, $\chi(G)=3$.

Uma clique é um conjunto de vértices todos adjacentes entre si. Se a maior clique tem tamanho $\omega(G)$, precisamos de pelo menos esse número de cores. Por outro lado, uma coloração gulosa usa no máximo $\Delta(G)+1$, onde $\Delta$ é o grau máximo: ao colorir um vértice, os seus vizinhos já coloridos proíbem no máximo $\Delta$ cores. Portanto:

$$\omega(G)\le\chi(G)\le\Delta(G)+1.$$

Os dois limites podem ser diferentes. Em $C_5$, a maior clique tem tamanho 2, mas o ciclo ímpar exige três cores.

Todo o grafo planar finito pode colorir-se com no máximo quatro cores. A recíproca é falsa: $K_{3,3}$ usa duas cores e não é planar. O número de cores também não decide se existe percurso de Euler ou de Hamilton.