# matching theory – Number of edges in bipartite graphs

Let $$G$$ be a bipartite graph on $$n$$ vertices of either color.

Suppose $$G$$ contains no perfect matching the number of edges can be $$Omega(n^2)$$ (just do not place an edge between a particular pair of vertices).

1. Suppose $$G$$ contains exactly one perfect matching what is the maximum number of edges it can have?

2. Suppose $$G$$ contains exactly two perfect matchings what is the maximum number of edges it can have?

I think $$2n-1$$ is the upper bound for 1. Essentially fix a perfect matching. As long as we do not have a $$2times2$$ subgraph we can add edges and there is exactly $$n-1$$ additional edges we can add. For 2. the upper limit is $$2n$$ I think by the same calculation.