####

#### Two short proofs concerning tree-decompositions

We give short proofs of the following two results: of Thomas's
theorem that every finite graph has a linked tree-decomposition
of width no greater than its tree-width, and of the `tree-width
duality theorem' of Seymour and Thomas that the tree-width of
a finite graph is exactly one less than the largest order of its
brambles.

Download (PDF)