We show that the number of perfect matchings in a simple graph G with an even number of vertices and degree sequence d1, d2,..., dn is at most ∏i=1n(di· !)1/2di. This bound is sharp if and only if G is a union of complete balanced bipartite graphs.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics
- Perfect matchings