MathCastle
Graph TheoryMediumEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Medium problem

In the complete bipartite graph K4,5K_{4,5} (sides of size 44 and 55), a Hamiltonian cycle is impossible (the sides are unequal), but a Hamiltonian PATH that visits every one of the 99 vertices is possible, since the side sizes differ by only 11. How many edges does such a path use?