Bounding the edges belonging to no perfect matching We are told to let $G = (X \cup Y, E)$ be a bipartite graph with $|X|=|Y|=n$, and to suppose that $G$ has a perfect matching. I am trying to find a way to prove that $G$ has at most $n \choose 2$ edges belonging to no perfect matching, and to construct examples that show that this bound is the best possible for every $n$. Any help would be greatly appreciated!
 A: Name the vertices with $X=\{x_i\mid i=1,\dots,n\}$ and $Y=\{y_i\mid i=1,\dots,n\}$ such that $M=\{\{x_i,y_i\}\mid i=1,\dots,n\}$ is a perfect matching. Assume, towards contradiction, that we have more than $\binom{n}{2}$ edges which is not in any perfect matching. Partition $E(G)\setminus M$ to $E_{i,j}=\{\{x_i,y_j\},\{x_j,y_i\}\}\cap E(G)$ for $i<j$ and $i,j\in\{1,\dots,n\}$ (Some part may be empty though). By our assumption (and pigeonhole principle), there is some pair $i<j$, $i,j\in\{1,\dots,n\}$, such that $E_{i,j}$ has two edges which are not in any perfect matching. This is a contradiction, since $(M\setminus \{\{x_i,y_i\},\{x_j,y_j\}\})\cup E_{i,j}$ is a perfect matching.
For tight example, let $X=\{x_i\mid i=1,\dots,n\}$, $Y=\{y_i\mid i=1,\dots,n\}$, $M=\{\{x_i,y_i\}\mid i=1,\dots,n\}$, $R=\{\{x_i,y_j\}\mid i<j,i,j=1,\dots,n\}$ and $G=(X\cup Y,M\cup R)$. Obviously, $M$ is a perfect matching for $G$. Claim that $M$ is the only one perfect matching. If it does not hold, then there exists some perfect matching which does not contain $e_i=\{x_i,y_i\}$ for some $i\in\{1,\dots,n\}$, But this is not possible, since $|\Gamma_{G-e_i}(\{x_1,\dots,x_i\})|=i-1<|\{x_1,\dots,x_i\}|$.
