Treewidth
![A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the tree. Each tree node lists at most three vertices, so the width of this decomposition is two.](/Images/godic/202502/17/Tree_decomposition.svg4906.png")
![A bramble of order four in a 3×3 grid graph, the existence of which shows that the graph has treewidth at least 3](/Images/godic/202502/17/3x3_grid_graph_haven.svg4906.png")
![The four forbidden minors for treewidth 3: K5 (top-left), the graph of the octahedron (bottom-left), the Wagner graph (top-right), and the graph of the pentagonal prism (bottom-right)](/Images/godic/202502/17/Partial_3-tree_forbidden_minors.svg4906.png")
In graph theory, the treewidth of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: from the size of the largest vertex set in a tree decomposition of the graph, from the size of the largest clique in a chordal completion of the graph, from the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or from the maximum order of a bramble, a collection of connected subgraphs that all touch each other.