Bramble (graph theory)

Summary

In graph theory, a bramble for an undirected graph $G$ is a family of connected subgraphs of $G$ that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in $G$ that has one endpoint in each subgraph. The order of a bramble is the smallest size of a hitting set, a set of vertices of $G$ that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of $G$.