Demostración: Suponga que G es un grafo conexo, y u son vértices particulares, pero arbitrariamente elegidos, de G. [Debemos demostrar que u y pueden ser conectados por una trayectoria.] Como G está conectada, existe un camino de a . Si el camino contiene un vértice repetido, entonces borre la parte del camino de la primera ocurrencia del vértice a su próxima ocurrencia. (Por ejemplo, en el camino e1 2e5 7e6 2e3 , el vértice 2 ocurre dos veces. Borrando la parte del camino de una ocurrencia a la próxima se obtiene e1 2e3 .) Si el camino resultante contiene un vértice repetido, entonces realice otra vez el proceso anterior de borrado. Vuelva a comprobar si hay un vértice repetido. Continúe de esta manera hasta que todos los vértices repetidos hayan sido borrados. (Esto ocurrirá eventualmente, porque es finito el número de vértices). El camino resultante conecta a con pero con ningún vértice repetido. Por el ejercicio 37(b), tampoco tiene algún extremo repetido. Así esta es una trayectoria de a .