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

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

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.