MathCastle
Graph TheoryMediumEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Medium problem

A graph on vertices 1,2,3,41,2,3,4 has edges 12,23,34,41,1312,23,34,41,13 (a square with one diagonal). It has an Euler trail running between 11 and 33 (its only two odd-degree vertices). Counting two trails as different whenever they use the edges in a different order, how many distinct Euler trails start at 11 and end at 33?