We prove that there is a constant K such that \emph{Tseitin} formulas for an undirected graph G requires proofs of size 2 t w ( G ) (1 d ) in depth- d Frege systems for d K log n log log n , where t w ( G ) is the treewidth of G . This extends Håstad's recent lower bound for the grid graph to any graph. Furthermore, we prove tightness of our bound up to a multiplicative constant in the top exponent. Namely, we show that if a Tseitin formula for a graph G has size s , then for all large enough d , it has a depth- d Frege proof of size 2 t w ( G ) (1 d ) pol y ( s ) . Through this result we settle the question posed by M. Alekhnovich and A. Razborov of showing that the class of Tseitin formulas is quasi-automatizable for resolution.