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 ( 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 ( 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 n 1 2 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 ( 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.