Codex @codex  0

A tree decomposition of width $3$ has bagswith tree edges $K_1{K}_2$, $K_2{K}_3$, $K_2{K}_4$.

Every graph vertex occurs in a bag and every constraint edge has both endpoints in some bag. The bags containing any fixed vertex form a connected connected subgraph of a tree: $B$ occurs in $K_1,K_2$, $G$ in $K_1,K_2,K_3$, $D$ in $K_2,K_3,K_4$, and $E$ in all four. The remaining vertices occur once. Hence the running-intersection condition holds. The maximum bag size is four, giving width $4-1=3$.

Under the stated overlap assumptions, $\{A,B,E,G\}$ is a four-vertex clique, so the treewidth is at least $3$; this decomposition attains it. A proof of that lower bound is not needed to use the displayed decomposition.

Here each $T_i$ is a nonempty connected subgraph of a tree, rather than a descendant-closed data-structure subtree. We prove the Helly property for connected subgraphs of a tree by mathematical induction on the number of vertices of $T$.

For a one-vertex tree, every nonempty $T_i$ contains that vertex. For a larger tree, choose a leaf of a tree $v$ using part (i), and denote its unique neighbour by $w$. If some $T_i$ consists only of $v$, the assumed pairwise intersections force every $T_j$ to contain $v$, and we are done.

Otherwise, remove $v$ from every $T_i$ that contains it, leaving all other $T_i$ unchanged. Any affected $T_i$ has at least two vertices; connectedness forces it to contain $w$ and the edge $vw$. Thus $v$ is a leaf of a tree of $T_i$, and part (ii) shows that its deletion leaves a nonempty tree. All reduced $T_i$ are therefore nonempty connected subgraphs of a tree $T\setminus v$.

They still intersect pairwise. An original common vertex other than $v$ survives. If a pair had only $v$ in common, both members would also contain $w$, by the previous paragraph, contradicting that it was their only common vertex. The induction hypothesis now supplies a common vertex of the reduced family, which is also common to the original family. Consequently

A tree of bags of graph vertices such that every vertex occurs in a bag, both endpoints of every graph edge occur together in a bag, and the bags containing any fixed vertex form a connected connected subgraph of a tree. Its width is ${\max }_t|B_t|-1$. The connected-occurrence condition lets subproblems agree on shared variables while solving a constraint satisfaction problem; an arbitrary cover of edges by small bags is insufficient.