ABSTRACT
We introduce the notion of a graph derangement, which naturally interpolates between perfect
matchings and Hamiltonian cycles. We give a necessary and sufficient
condition for the existence of graph derangements on a locally finite graph.
This result was first proved by W. T. Tutte in 1953 by applying some deeper
results on digraphs. We give a new, simple proof which amounts to a reduction
to the (Menger-Egerváry-K?nig-)Hall(-Hall) Theorem on transversals of set
systems. We also consider the problem of classifying all cycle types of graph
derangements on m × n checkerboard graphs. Our presentation does
not assume any prior knowledge in graph theory or combinatorics: all
definitions and proofs of needed theorems are given.
Share and Cite:
Clark, P. (2013) Graph Derangements.
Open Journal of Discrete Mathematics,
3, 183-191. doi:
10.4236/ojdm.2013.34032.