Euler, Hamilton, planaridade e coloração

Euler

Um trilho de Euler usa todas as arestas exatamente uma vez; um caminho de Hamilton visita todos os vértices exatamente uma vez. Os percursos fechados voltam à origem.

Para um grafo não dirigido, os critérios exigem que os vértices com arestas fiquem na mesma componente. Então:

• Há circuito de Euler se e só se todos os graus são pares.
• Há trilho aberto se e só se há dois vértices de grau ímpar, que são os extremos do trilho.
• Para construir, percorre sem repetir arestas e intercala novos circuitos onde sobram arestas.
• Sem arestas, o percurso sem passos parte de qualquer vértice.

Não há critério de paridade para Hamilton. Um grafo desconexo impede um caminho abrangente; um vértice de grau 1 ou uma articulação impede um ciclo.

Na borboleta, $a,b,c,d,e,c,a$ é um circuito de Euler. Não há ciclo de Hamilton, pois remover $c$ separa os triângulos. Há caminho $a,b,c,d,e$.

Bipartição

Um grafo é bipartido quando os vértices se dividem em duas partes disjuntas com cada aresta entre as partes. Isso equivale a ser 2-colorível; a parte vazia é permitida sem arestas.

• Um grafo é bipartido se e só se não tem ciclos ímpares. Árvores e ciclos pares são bipartidos.
• Um ciclo de Hamilton num bipartido exige partes iguais; a igualdade não garante o ciclo.
• $K_{m,n}$ tem $mn$ arestas. Um bipartido simples com $v$ vértices tem $e\le\lfloor v^2/4\rfloor$.

Planaridade

Um grafo é planar quando admite um desenho sem cruzamentos fora de extremos comuns. Os cruzamentos de um desenho particular não provam impossibilidade.

Desenho com cruzamento

Desenho sem cruzamentos

Com $v$ vértices, $e$ arestas, $f$ faces e $c$ componentes não vazias, incluindo a face exterior:

$$v-e+f=1+c.$$

No caso conexo o segundo membro dá 2; uma árvore tem uma face. Para um grafo simples planar com $v\ge3$:

• $e\le3v-6$.
• Sem triângulos, incluindo o caso bipartido: $e\le2v-4$.

$K_5$ viola o primeiro limite ($10>9$); $K_{3,3}$ viola o segundo ($9>8$). Cumprir estes limites necessários não basta para provar planaridade; um desenho sem cruzamentos basta para provar que o grafo é planar.

Coloração

Uma coloração própria dá cores distintas aos extremos de cada aresta. O número cromático $\chi(G)$ é o mínimo; prova-o com uma coloração e uma razão que exclua menos cores.

Grafo	$\chi$
$K_n$	$n$
$C_n$, $n\ge3$	2 se par, 3 se ímpar
$K_{m,n}$, $m,n\ge1$	2
Sem arestas, não vazio	1

Com clique máxima $\omega(G)$ e grau máximo $\Delta(G)$:

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

A borboleta exige três cores por causa do triângulo; $c$ com uma cor e os pares $a,d$ e $b,e$ com as outras duas chegam. Um grafo planar finito usa no máximo quatro cores; a recíproca falha, pois $K_{3,3}$ usa duas cores e não é planar.

Construções de percursos e limites de planaridade.