Graph TheoryMediumEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Medium problem
In the complete bipartite graph (sides of size and ), a Hamiltonian cycle is impossible (the sides are unequal), but a Hamiltonian PATH that visits every one of the vertices is possible, since the side sizes differ by only . How many edges does such a path use?