# zbMATH — the first resource for mathematics

Two short proofs concerning tree-decompositions. (English) Zbl 1018.05081
The authors give a short and nice proof of the key theorem of R. Thomas [J. Comb. Theory, Ser. B 48, 67-76 (1990; Zbl 0636.05022)] which states that any finite graph $$G$$ admits a tree-decomposition of width the treewidth of $$G$$ which is linked. A tree-decomposition of $$G$$ is linked if, for every $$k\geq 0$$ and any two of its pieces $$P$$ and $$Q$$, either there are $$k$$ disjoint paths between $$P$$ and $$Q$$ or there is a third piece $$R$$ between $$P$$ and $$Q$$ with at most $$k-1$$ vertices.
The proof relies on a basic lemma which also provides a short derivation of the tree-width duality theorem of Seymour and Thomas saying that the treewidth of a graph equals the maximum $$k$$ such that there is a collection of connected subgraphs, pairwise intersecting or adjacent, such that no set of at most $$k$$ vertices meets all of them.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: