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.