In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant.

The concept of treewidth was originally introduced by Umberto Bertelè and Francesco Brioschi (1972) under the name of dimension. It was later rediscovered by Rudolf Halin (1976), based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by Neil Robertson and Paul Seymour (1984) and has since been studied by many other authors.

A tree decomposition of a graph ${\displaystyle G=(V,E)}$ is a tree ${\displaystyle T}$ in which each node is associated with a subset of vertices called a "bag". (The term node is used to refer to a vertex of ${\displaystyle T}$ to avoid confusion with vertices of ${\displaystyle G}$). The bags ${\displaystyle X_{1},\dots X_{t}}$ must satisfy the following properties:

The width of a tree decomposition is the size of its largest bag ${\displaystyle X_{i}}$ minus one. The treewidth ${\displaystyle \operatorname {tw} (G)}$ of a graph ${\displaystyle G}$ is the minimum width among all possible tree decompositions of ${\displaystyle G}$. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.

Equivalently, the treewidth of ${\displaystyle G}$ is one less than the size of the largest clique in the chordal graph containing ${\displaystyle G}$ with the smallest clique number. A chordal graph with this clique size may be obtained by adding to ${\displaystyle G}$ an edge between every two vertices for which at least one bag contains both vertices.

Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit–evasion game defined on a graph. A graph ${\displaystyle G}$ has treewidth ${\displaystyle k}$ if and only if it has a haven of order ${\displaystyle k+1}$ but of no higher order, where a haven of order ${\displaystyle k+1}$ is a function ${\displaystyle \beta }$ that maps each set ${\displaystyle X}$ of at most ${\displaystyle k}$ vertices in ${\displaystyle G}$ into one of the connected components of ${\displaystyle G\setminus X}$and that obeys the monotonicity property that ${\displaystyle \beta (Y)\subseteq \beta (X)}$ whenever ${\displaystyle X\subset Y}$.