Show that $pw(T_{d}) \geq d- 1$. Feel free to suggest a completely different approach, if you know of a better one.

A complete ternary tree $T_{d}$ is a rooted tree in which each vertex has a 3 descendants and has depth $d$. Depth $d$ indicates the distance from the root vertex to a vertex at the deepest level of a tree. For example the complete ternary tree $T_{1}$ is a root node with 3 descendants (a 3 claw tree).

A path decomposition of a tree is a tree decomposition, in which the resulting tree is a path. Path width is defined as the bag with the largest amount of vertices minus 1.

My attempt:

I have attempted the problem through induction on $d$. The claim holds trivially for $d=1$ and $d=2$, as any connected graph must have $pw \geq 1$. Any edge in a connected graph must be in some bag, meaning there exists a bag with 2 vertices. Suppose the claim holds for depth $<d$. The tree $T_{d}$ is formed of a root vertex $v_{0}$ and three connected components, all of which are complete ternary trees of depth $d-1$. In other words the tree $T_{d}$ is formed of 3 tress $T_{d-1}$ and a root vertex $v_{0}$. By the induction hypothesis the path width of $T_{d-1}$ must be $\geq d-2$.

How can I calculate the path width of $T_{d}$ given that I know that I have 3 subtrees of path width $d-2$?


Here's a sketch: The key idea is that a path decomposition which covers all three principal subtrees of $T_d$ must pass through the subtrees in some order, and it has to "thicken" the middle one a bit.

Call the three subtrees of $T_d$ adjacent to the root $a$, $b$, and $c$, and let $P=(\mathcal{B},E)$ be a tree decomposition of $T_d$ which is a path, having bags $B$ and edges $E$. The induction step follows from these observations:

  • $P$ contains tree decompositions of each of $a,b,c$. By the induction hypothesis, there are corresponding bags $B_a, B_b, B_c \in \mathcal{B}$ having at least $d$ vertices of the respective subtree.
  • $P$ also has bags $B_a', B_b', B_c' \in \mathcal{B}$ which contain the root of $T_d$ (called $v_0$ in the OP) and the respective roots of $a, b, c$.

We have a dichotomy. Either:

  • One of $B_a, B_b, B_c$ (say $B_a$) lies in between two of $B_a', B_b', B_c'$ in the path $P$, so that by the properties of tree decompositions, we must have the root vertex $v_0\in B_a$. Thus $|B_a|\ge d+1$, and we are done.


  • If the preceding does not hold, then one of $B_a, B_b, B_c$, say $B_a$, must lie in between $B_b$ and $B_b'$ or between $B_c$ and $B_c'$ in the path $P$. WLOG suppose $B_a$ lies between $B_b$ and $B_b'$. Then $B_a$ must contain a vertex of subtree $b$ (otherwise there would a vertex of $b$ on both sides of $B_a$ in $P$ with no connecting path). So again $|B_a|\ge d+1$, as desired.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.