Treewidth of two complete binary trees joined at their leaves

Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ be the graph obtained from $G'$ where for every leaf $x$, an edge between $x_1, x_2$ is introduced.

I am interested in the treewidth of $G$. I conjecture that it is $O(\log(n))$ (start at the root of one copy of a tree, then first visit the left subtree and recurse until the root node of the other tree is reached, we always need to keep track of a path of length at most $\log(n)$). First, is this correct? Second, how can I prove a LB on the treewidth of this graph?

Thanks in advance.

• What would prevent this graph from being series-parallel? – Gamow Mar 21 '17 at 14:24
• Thanks, I am new to treewidth and I missed this. The treewidth is hence 2. I would still be interested to see how the actual decomposition looks like. – Chris Mar 21 '17 at 14:51
• For graphs up to 150 vertices you can use treedecompositions.com to find and visualize a reasonable heuristic decomposition. – Fasermaler Mar 21 '17 at 20:12

1 Answer

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT." Theoretical Computer Science 351.3 (2006): 296-302. The graph structure they use unifies leaves with the same label (rather than putting an edge between them), but their graph can be obtained from yours by suppressing degree-2 vertices, and this does not impact upon the treewidth.