Perfect matchings and derangements on graphs

Matija Bucic, Pat Devlin, Mo Hendon, Dru Horne, Ben Lund

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)340-354
Number of pages15
JournalJournal of Graph Theory
Issue number2
StatePublished - Jun 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • perfect matchings
  • permanent
  • permutations


Dive into the research topics of 'Perfect matchings and derangements on graphs'. Together they form a unique fingerprint.

Cite this