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.
 P. R. Halmos and H. E. Vaughan, “The Marriage Problem,” American Journal of Mathematics, Vol. 72, No. 1, 1950, pp. 214-215. http://dx.doi.org/10.2307/2372148
 M. Hall Jr., “Distinct Representatives of Subsets,” Bulletin of the American Mathematical Society, Vol. 54, No. 10, 1948, pp. 922-926.
 C. J. Everett and G. Whaples, “Representations of Sequences of Sets,” American Journal of Mathematics, Vol. 71, No. 2, 1949, pp. 287-293.
 W. T. Tutte, “The Factorization of Linear Graphs,” Journal of the London Mathematical Society, Vol. 22, No. 2, 1947, pp. 107-111.
 W. T. Tutte, “The Factorization of Locally Finite Graphs,” Canadian Journal of Mathematics, Vol. 2, No. 1, 1950, pp. 44-49.