Graph Theory & Treewidth

Brambles and tangles

How you prove a graph's treewidth is large, not just small.


The duality

Finding a narrow tree decomposition proves treewidth is small. To prove it is large you need a witness in the other direction — and that witness is a bramble. A bramble is a collection of mutually touching connected subgraphs; its order is the smallest set of vertices hitting all of them. The bramble number equals treewidth plus one. This is Seymour and Thomas's treewidth duality theorem.

Tangles are the closely related object that organizes the high-connectivity structure of a graph and underpins the graph-minors theory of Robertson and Seymour. Both brambles and tangles formalize the same idea: a region of the graph that cannot be separated cheaply.

The shadow–mirror reading

A bramble is the inseparable core — the part of the structure that no small cut can pull apart. In the thesis's language it is exactly the irreducible coupling: the width is large precisely because there is a whole that resists decomposition into shadow and mirror.

Questions

What is the bramble number?

The maximum order of any bramble in the graph. By Seymour–Thomas it equals treewidth + 1, giving an exact lower-bound certificate.

Are tangles and brambles the same?

Closely related but distinct. Both certify high connectivity; tangles are central to graph-minor theory, brambles give the cleanest treewidth duality.

Read the volume (PDF, 895 pp)More in Graph Theory & Treewidth