Em um grafo conexo, quando existe uma trilha euleriana e, se houver exatamente dois vértices de grau ímpar, onde ela começa e termina?

Um grafo conexo tem trilha euleriana se tiver 0 ou 2 vértices de grau ímpar; com 2 vértices ímpares, a trilha começa em um vértice ímpar e termina no outro.

Explicação:
O critério de Euler afirma que uma trilha que percorre todas as arestas exatamente uma vez existe somente quando o grafo conectado possui 0 ou 2 vértices de grau ímpar.
Se são 2, os únicos extremos possíveis da trilha são esses dois vértices ímpares; se são 0, existe um circuito euleriano (começa e termina no mesmo vértice).

Exemplo:
Considere um grafo com vértices 1,2,3,4 e arestas 12, 23, 34, 24.
Calculando graus: \(deg(1)=1,\; deg(2)=3,\; deg(3)=2,\; deg(4)=2\).
Há exatamente dois vértices de grau ímpar: 1 e 2. Portanto existe uma trilha euleriana que começa em 1 e termina em 2. Um percurso que usa todas as arestas sem repeti-las é: 1 → 2 → 4 → 3 → 2.