The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is the number of vertices in $G_n$. This lower bound matches with the upper bound $2^{O(n)}$ up to an application of a polynomial. Our result implies the $2^{\Omega(n)}$ lower bounds for the complete graph $K_n$ and the complete bipartite graph $K_{n, O(n)}$ that improve the lower bounds followed from [Raz04]. Our results also implies the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph.

We also prove the following corollary. For every natural number $d$, for every $n$ large enough, for every function $h:\{1,2,\dots, n\}\to \{1,2,\dots, d\}$, we construct a graph with $n$ vertices that has the following properties. There exists a constant $D$ such that the degree of the $i$-th vertex is at least $h(i)$ and at most $D$, and it is impossible to make all degrees equal to $h(i)$ by removing the graph's edges. Moreover, any proof of this statement in the resolution proof system has size $2^{\Omega(n)}$. This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph.