Considere o grafo planar topológico
G do problema anterior.
Sejam G* o dual de
G e
G' o grafo que se obtem de
G* removendo
o vértice associado à face ilimitada juntamente com todas as arestas nele
incidentes.
- Veja se, no grafo
G, existem cadeias eulerianas
ligando os vértices A e C.
E conectando o par de vértices B, D?
- Diga se existem ciclos hamiltonianos em G.
- Represente o grafo planar topológico
G'.
- Qual o número cromático de G?