# What's the connection between branchwidth and treewidth

I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $$branchwidth(G) = Θ(treewidth(G))$$.

However, my question pertains to a specific case involving Tseitin formulas.

The underlying graph of Tseitin formulas is denoted by $$G$$.

And the underlying hypergraph is denoted by $$G'$$ where each edge in the hypergraph corresponds to a clause of formulas. $$G$$ and $$G'$$ can be seen as dual graphs, although a vertex in $$G$$ may correspond to multiple edges in $$G'$$.

Myquestion: What's the connection between $$branchwidth(G')$$ and $$treewidth(G)$$

My question comes from two papers, in Characterizing Tseitin-formulas with short regular resolution refutations, it stated that:

"The upper bound for this result was already known from [2] where it is shown that, for every graph G, unsatisfiable Tseitin-formulas with the underlying graph G have regular resolution refutations of length at most $$2^{O(tw(G))}|V (G)|^c$$ where c is a constant."

However, upon checking the reference, I noticed that it uses $$branchwidth(G')$$ rather than $$treewidth(G)$$.

• They differ by a factor $O(\Delta(G))$ where $\Delta(G)$ is the maximal degree of $G$. In the context of Tseitin formulas, it is usually assumed that the degree is constant, so this factor is dropped. Mar 6, 2023 at 19:46
• @ArturRiazanov I would like to clarify if the definition of tree decomposition on hypergraph is as shown in NEIL ROBERTSON & SEYMOUR .1991.p168.. If this is the correct definition, I believe that the tree decomposition you obtained form $G$ to $G'$ by substituting every vertex of $G$ by the variables of the incident edges may not satisfy condition (ii)
– Jxb
Mar 7, 2023 at 3:23
• @ArturRiazanov Oh I understand your comment finally. step1: for a same graph, treewidth is somewaht equals to branchwidth. step2: For a CNF, the treewidth of underlying hypergraph and primal graph is the same. step3: for Tseitin formulas, the treewidth of its primal graph and underlying grapg just differ by a factor $O(\Delta(G))$
– Jxb
Aug 2, 2023 at 15:52