We show that each perfect matching in a bipartite graph (Formula presented.) intersects at least half of the perfect matchings in (Formula presented.). This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- perfect matchings