<p>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.</p>

CC BY-SA 3.0
2017-03-21T14:55:57.517Z
2017-03-21T14:55:57.517Z
steven kelk
<p>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.</p>

<p>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?</p>

<p>Thanks in advance. </p>

CC BY-SA 3.0
2017-03-21T14:24:51.457Z
What would prevent this graph from being series-parallel?
Gamow
CC BY-SA 3.0
2017-03-21T14:51:58.483Z
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
CC BY-SA 3.0
2017-03-21T20:12:16.063Z
For graphs up to 150 vertices you can use http://treedecompositions.com/ to find and visualize a  reasonable heuristic decomposition.
Fasermaler
<treewidth><binary-trees>
Treewidth of two complete binary trees joined at their leaves
Chris
# Treewidth of two complete binary trees joined at their leaves

(Asked by: username_0 on 2017-03-21)

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.

**Tags:** treewidth, binary-trees

> **Comments:**
> **username_1**: What would prevent this graph from being series-parallel?  
> **username_0**: 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.  
> **username_2**: For graphs up to 150 vertices you can use http://treedecompositions.com/ to find and visualize a  reasonable heuristic decomposition.  

---

## 1 answers

### Answer by username_3 on 2017-03-21. Score: 5

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.


---

