Show that a complete ternary tree of depth d has path width >= d-1

combinatoricsgraph theorytrees

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$?

Best Answer

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.

Or:

  • 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.
Related Question