Primeira postagem e o primeiro teorema sobre grafos.

Esta é a primeira postagem do blog Tiorema! Pretendo, neste espaço, postar algumas coisitas matemáticas que acho interessante. Tem tanta coisa que nem sei bem por onde começar. Como gosto muito de combinatória, decidi começar por um dos primeiros teoremas em Teoria dos Grafos: o Teorema de Euler. O leitor que não conhece ainda a Teoria dos Grafos ou que não está muito familiarizado com as definições e notações poderá ler um post que preparei com as principais noções que usarei ao falar de grafos [link], apesar de que neste post a principal definição será feita logo no próximo parágrafo de modo que um conhecimento básico de grafos já é suficiente para uma boa leitura deste texto.

Dado um grafo $G=(V,E)$, um passeio (de tamanho $k$) em $G$ é uma sequência alternada de vértices e arestas

$$P = v_0 e_1 v_1 e_2 v_2 \ldots  v_{k-1} e_{k} v_k,$$

com $v_0, v_i\in V$ e $e_i = \{v_{i-1},v_{i}\} \in E$, pra todo $1 \leq i \leq n$. Os vértices $v_i$ não precisam todos serem distintos; quando são, $P$ é chamado de caminho. Quando as aresta $e_i$ são todas distintas, dizemos que $P$ é uma trilha. Quando $v_0 = v_k$, dizemos que $P$ é um passeio fechado; se $P$ for uma trilha, dizemos que ele é uma trilha fechada. Uma trilha fechada cujos os vértices $v_i$, para $i \geq 1$, são distintos é chamado de ciclo.

Uma trilha fechada $P$ é um circuito Euleriano do grafo $G$ se todas as arestas de $G$ estiverem em $P$. Em outras palavras, queremos percorrer todo o grafo através das arestas começando de um vértice e voltando, no fim, para o mesmo vértice, mas sem passar pela mesma aresta duas vezes. Um grafo que contém um circuito Euleriano é dito ser um grafo Euleriano.

Euler se interessou por esse tipo de passeio quando se questionou se era possível visitar todas as quatro regiões da cidade Königsberg (território da Prússia até 1945, atual Kaliningrado). Estas quatro regiões eram conectadas por sete pontes (ver figura abaixo). Mas Euler não queria visitá-las de qualquer maneira, ele queria passar por cada ponte exatamente um vez.

Esse problema pode ser transcrito na linguagem de grafos! Considere o grafo da figura abaixo. Cada vértice do grafo representam uma região de Königsberg e cada aresta representam uma ponte que conectam duas dessas regiões.

O leitor deve observar que segundo a nossa definição de grafo, o grafo da figura acima não é um grafo para nós. De fato, este grafo contém arestas múltiplas. Mas este problema pode ser contornado subdividindo algumas arestas deste grafo, como na figura abaixo.

O leitor deverá se convencer que se conseguirmos um circuito Euleriano no grafo da figura acima, também conseguiremos um circuito Euleriano no primeiro grafo e consequentemente conseguiremos o tão desejado passeio de Euler sobre a cidade de Königsberg. Então resolver o problema de Euler sobre as pontes de Königsberg é equivalente a mostrar que existe ou não um circuito Euleriano no grafo da figura acima.

Euler, como todo matemático, não ficou satisfeita em resolver este problema em particular. Ele decidiu resolver o problema para qualquer grafo e assim obteve o que hoje chamamos de

Teorema de Euler. Seja $G$ um grafo conexo. O grafo $G$ é Euleriano se, e somente se, todo vértice de $G$ possui grau par.

Para provar o Teorema de Euler, usaremos o seguinte

Lema. Um grafo conexo com pelo menos dois vértices e tal que todo vértice possui grau par, contém um ciclo.

Demonstração. Seja $G=(V,E)$ um grafo conexo com pelo menos dois vértices e com todo vértice de $G$ tendo grau par. Todo vértice de $G$ tem grau positivo, do contrário, $G$ não seria conexo ou seria formado por apenas um vértice. Então todo vértice tem pelo menos grau $2$. Segue que 

$$|E| = \frac{1}{2}\sum_{v\in V} d(v) \geq \frac{1}{2} \sum_{v\in V} 2 = |V|$$

Então $G$ não é uma árvore, pois se fosse, teríamos $|E| = |V| -1$. Logo, $G$ contém um ciclo.

$\square$

Agora podemos provar o Teorema de Euler.

Demonstração do Teorema de Euler. Seja $G = (V,E)$ um grafo conexo com $n$ vértices e $m$ arestas. Suponha que exista um circuito Euleriano $$P = v_0 e_1 v_1 e_2 v_2 \ldots  v_{m-1} e_{m} v_k,$$ em $G$. Todo vértice de $G$ aparece em $P$. Suponha que um vértice $v$ de $G$ apareça $k$ vezes em $P$, então o grau de $v$ deverá ser $2k$. Logo, todo vértice de $G$ possui grau par.

Suponha agora que todo vértice de $G$ possui grau par. Provamos que $G$ é Euleriano por indução sobre $m$, o número de arestas de $G$. Se $G$ possuir apenas um vértice, o grau deste vértice é par e para efeitos técnicos, consideramos que neste caso $G$ possui um circuito Euleriano: aquele formado por apenas um vértice e nenhuma aresta. O menor número de arestas de um grafo não-trivial com todos os seus vértices com grau par é 3 e corresponde ao $K_3$. Verifica-se trivialmente que $K_3$ é Euleriano. Suponha, então, que $m>3$ e que todo grafo com menos de $m$ arestas e com todos os seus vértices possuindo grau par seja Euleriano. Provemos que $G$ também é.

O Lema 1 nos garante que $G$ contém um ciclo. Seja, então, $C$ um ciclo em $G$. Considere $G' := G \setminus C$ o grafo obtido a partir de $G$ deletando as arestas do ciclo $C$. Cada vértice do grafo $G'$ ainda possui grau par, uma vez que cada vértice de $C$ é incidente com duas arestas de $C$ e, portanto, ao deletarmos tais arestas, o grau dos vértices em $C$ irá diminuir duas unidades. Sejam $G_1,G_2, \ldots ,G_r$ as componentes conexas de $G'$. Uma vez que $|G_i|<m$, qualquer que seja $i\in \{1, \ldots ,r\}$, temos que pela hipótese de indução, $G_i$ contém um circuito Euleriano $P_i$.

Agora construímos um circuito Euleriano $P$ em $G$. Seja $v_1$ um vértice qualquer de $C$ e fixe uma orientação no circuito $C$ a qual iremos seguir em direção. Sem perda de generalidade, podemos supor que $G_1$ é a componente conexa em $G'$ que contém $v_1$. Seja agora $v_2$ o primeiro vértice de $C$, seguindo a orientação fixada, que não pertença a componente $G_1$ e digamos que $G_2$ é a componente que o contém. Seja $v_3$ o primeiro vértice, seguindo a orientação fixada, que não pertence a componente $G_1$ nem $G_2$ e digamos que $G_3$ é a componente que o contém. E analogamente definimos os vértices $v_1, v_2, \ldots , v_r$. Definimos o passeio $P$ sobre $G$ como sendo

$$P := v_1 P_1 v_1 C v_2 P_2 v_2 C v_3 P_3 v_3 C \ldots C v_r P_r v_rC v_1$$

É de verificação imediata que este circuito é Euleriano.

$\square$

Referências:

[1] Diestel, Graph Theory. 3nd edition.