A note on a question of C. D. Savage
Consider a graph \(G\) and a fixed orientation of a subset \(E\) of the edge set of \(G\). Then consider a new bipartite graph whose vertices are all acyclic orientations which extend the orientation of \(E\). Two vertices in the new graph are neighbors, if their orientations disagree on precisely one edge. The author shows that such a graph need not have a Hamiltonian path even when the cardinalities of the two bipartite classes differ by only \(1\).
scientific article