A Menger-like property of tree-width: The finite case (Q1097894): Difference between revisions

The notion of tree-width was introduced by Robertson and Seymour. A graph has tree-width \(\leq w\) if it admits a tree-decomposition of tree-width \(\leq w\). We prove here that if G is finite and has tree-width \(\leq w\) then it admits a tree-decomposition of tree-width \(\leq w\) which satisfies a certain Menger-like condition. This result simplifies and generalizes a similar one of Robertson and Seymour. Its advantage is that it can be easily extended to infinite graphs and this extension is used in [\textit{R. Thomas}, Well-quasi-ordering infinite graphs with forbidden finite planar minor, Trans. Am. Math. Soc. (to appear)].