Trazabilidad de gráficas

Si una gráfica no tiene vértices finales , puede preguntarse lo siguiente: es posible trazar sobre todas las orillas en la gráfica exactamente una vez , sin levantar su lápiz? Por ejemplo, es trazable la gráfica mostrada a continuación?

El matemático suizo Leonhard Euler (un gran nombre en la historia de las matemáticas) resolvió este problema razonando como se explica a continuación.

Cada vez que toma su lápiz a través de un vértice, usa dos orillas: una hacia adentro, y la otra hacia afuera. Los vértices con grados impares son los que causan problemas: la única forma de lidiar con estos, es comenzar trazando o terminar trazando allí. Así, una gráfica no es trazable si tiene más de dos vértices de grado impar.

Por este teorema, la gráfica anterior no es trazable, ya que todos los cuatro vértices tienen grado impar (5, 3, 3, y 3).

Euler realmente probó la conversa del teorema también: cada gráfica sin vértices finales y con dos o menos vértices de grado impar es trazable.