Universidade Tecnológica Federal do Paraná
Professor Murilo V. G. da Silva
Notas de aula – Matemática Discreta (Aula 16)
Teoria dos Grafos (cont.)
Vamos provar agora dois teoremas que enunciamos em aulas passadas,
mas que ainda não haviam sido provados.
Teorema: Um grafo G conexo é euleriano ⇔ o grau de todo vértice de G é
par e maior ou igual a 2.
Prova da ida (⇒):
Suponha que G é conexo e euleriano. Seja C um circuito euleriano de G
e seja v um vértice (arbitrário) de G. Como G é conexo d(v) ≥ 2. Como C
percorre todas as arestas do grafo, em particular C percorre todas as arestas
incidentes a v. Cada vez que o circuito passa por v duas arestas incidentes
a v são percorridas (uma aresta de “entrada” e uma aresta de “saı́da”) e
portanto o grau de v deve ser par. Como v é arbitrário, esse raciocı́no pode
ser aplicado a todo vértice do grafo, e portanto todo vértice de G tem grau
par maior ou igual a 2.
Prova da volta (⇐):
Suponha que ∀v ∈ V (G), d(v) é par e maior ou igual a 2. Como G não
tem vértices de grau 1 pela QUESTÃO 5 da lista de exercı́cios 13 G não é
uma árvore e portanto contém pelo menos um ciclo C 0 .
Construiremos agora um circuito euleriano a partir do ciclo C 0 . Para tal
usaremos indução forte em m, onde m é o número de arestas de G.
BASE: Primeiramente precisamos saber qual é o menor m possı́vel neste
cenário. Como todo vértice tem grau maior ou igual a 2, sabemos que o
grafo não pode conter 0, 1 ou 2 arestas. Portanto a base é m = 3. O
único grafo com 3 arestas satisfazendo essas restrições (ter todo vértice com
grau maior ou igual a 2) é o K3 e este grafo obviamente contém um circuito
euleriano.
1
H.I.: Suponha que a proposição é válida para todo grafo com m arestas ou
menos.
INDUÇÃO: Seja G um grafo com m + 1 arestas. O ciclo C 0 (como qualquer
outro ciclo) deve ter pelo menos 3 arestas. Seja G0 o grafo obtido a partir da
remoção das arestas de G que fazem parte de C 0 . O grafo G0 resultante pode
ou não ser conexo. Seja G01 , G02 , ..., G0k os componentes conexos de G0 (observe
que se G0 é conexo, então k = 1). Como todo grafo G0i =, i = 1, 2, ..., k, tem
menos que m arestas, pela hipótese de indução todos eles contém um circuito
euleriano Ci0 ou G0i é um vértice isolado. Observe também que Ci0 contém pelo
menos um vértice de C 0 .
Para cada i = 1, 2, ..., k, considere agora o passeio Pi0 no grafo G0i : Dado o
circuito euleriano Ci0 = ui , v1 , ..., vs , ui em Gi , defina Pi0 = v1 , ..., vs . Digamos
que o ciclo C 0 tem t vértices, ou seja, C 0 = c1 , ..., ct , c1 . Construı́mos um
circuito euleriano em G da seguinte maneira: Começamos o circuito pelo
vértice c1 . Seguimos percorremos os vértices c1 , c2 , ..., ct , c1 , mas cada vez
que encontramos um vértice cj de C que pertença a um grafo G0i , antes de
seguir para cj+1 , fazemos um “desvio” e incluı́mos no circuito o passeio Pi0 .
Seguimos com esse processo até que retornemos ao vértice c1 . 2
Teorema: G é bipartite ⇔ G não contém nenhum ciclo ı́mpar.
Prova (⇒):
Suponha que G seja bipartite com as partições V1 e V2 . Todo passeio em
G alterna entre os vértices de V1 e V2 . Portanto todo passeio saindo de um
vértice (arbitrário) v, no caso de passar novamente em v, passará após um
número par de arestas percorridas. Portanto se G contém um ciclo C, como
C em particular também é um passeio, temos que C tem um número par de
arestas e portanto é um ciclo par.
Prova (⇐):
Suponha que G não contém nenhum ciclo ı́mpar. Podemos assumir que G
é conexo (pense a respeito desta afirmação). Seja v um vértice (arbitrário).
Vamos particionar V (G) em 2 conjuntos A e B descritos a seguir:
2
A: Conjunto de vértices u ∈ V (G) tal que o caminho mı́nimo entre u e v
é ı́mpar.
B: Conjunto de vértices w ∈ V (G) tal que o caminho mı́nimo entre w e v
é par.
Note primeiramente que v ∈ B. Suponha existam a1 , a2 ∈ A tal que a1 a2
é uma aresta. Como G é conexo, existe um passeio v, ..., a1 , a2 , ..., v. Mas
esse passeio contém um número ı́mpar de arestas. Pela QUESTÃO 1 da lista
de exercı́cios 16, G contém um ciclo ı́mpar, uma contradição. Portanto a1 e
a2 não são adjacentes. Com isso não existe nenhuma aresta ligando vértices
de A. Usando o mesmo argumento, não existem arestas conectando vértices
de B e portanto {A, B} é uma bipartição de G.
3