A solução de Euler consistia em descobrir em que tipos de grafos se poderia fazer certo caminho passando por todas as arestas uma única vez. Nasce ...

A solução de Euler consistia em descobrir em que tipos de grafos se poderia fazer certo caminho passando por todas as arestas uma única vez. Nasce daí o “Caminho de Euler” e o “Grafo de Euler”. Sobre esse assunto, podemos afirmar:

I-Teorema: um grafo conexo pode ser considerado Grafo de Euler se, e somente se, seus vértices são de grau par.
II-Prova: chega-se a um vértice “entrando” por uma aresta e encontrando outra aresta para “sair”, e continuar o caminho. Ou seja, duas linhas são necessárias para atravessar, uma linha para entrar e outra para sair. Cada vértice tem um par de linhas.
III-O Grafo das Pontes não tem solução pois apresenta um número ímpar de vértices.
a) Apenas I e II.
b) Apenas I e III.
c) Apenas II e III.
d) I, II e III.