We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an n n grid graph has size at least 2 ( n ) . Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph G ( V E ) any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on G has size at least 2 ( t w ( G ) ) for all 1 36 , where t w ( G ) is the treewidth of G (for planar graphs and some other classes of graphs the statement holds for = 1 ). We also show an upper bound O ( E 2 p w ( G ) ) , where p w ( G ) is the pathwidth of G .We apply the mentioned results in the analysis of the complexity of derivation in the proof system OBD D ( r eorderin g ) and show that any OBD D ( r eorderin g ) -refutation of an unsatisfiable Tseitin formula based on a graph G has size at least 2 ( t w ( G ) ) .