Skip to main content

All Questions

Filter by
Sorted by
Tagged with
11 votes
2 answers
1k views

Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$? Are examples of such extremal ...