The treewidth of a graph is one less than the smallest possible maximum bag size among its tree decompositions. Determining the treewidth of an arbitrary graph is an NP-hard problem. However, many NP-hard problems on graphs of bounded treewidth can be solved in polynomial time.
An empty graph has treewidth 0, while a tree or forest containing an edge has treewidth 1. Graphs with treewidth at most 2 correspond to series-parallel graphs. Every Halin graph has treewidth 3 (Bodlaender 1988).
The treewidth of a disconnected graph is equal to the maximum of the treewidths of its connected components.
A maximal graph with treewidth 
is called a 
-tree, while a graph with treewidth 
are known as partial 
-trees.
Graphs with treewidth 
may be characterized by a finite set of forbidden
minors, as summarized in the following table. For the case of 
, more than 75 minimal forbidden minors of widely varying
structures are known (Sanders 1993, Sanders 1995, Chlebiková 2002).
| treewidth bound | forbidden minors |
| 1 |  |
| 2 |  |
| 3 |  ,
octahedral graph  , prism graph  , Wagner graph  |
| 4 | unknown finite number of minors; at least 75 known |
The scramble number is the most powerful known lower bound on the gonality of a graph and satisfies
 |
(1)
|
where 
is the vertex
connectivity, 
is the edge connectivity, 
is the scramble number,
and 
is the gonality
of 
(Harp et al. 2020, Echavarria
et al. 2021).
For a graph with treewidth 
,
 |
(2)
|
(Dujmovic and Wood 2007), where 
is the book thickness.
Special cases include
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(9)
|
where 
denotes any tree,
any Halin
graph, 
is a cycle graph, 
is a complete graph, 
is a complete
bipartite graph, and 
is an 
grid
graph.
Chudnovsky et al. (2026) construct graphs showing that several natural restrictions do not force bounded treewidth. There are fixed positive integers 
and 
such that, for every positive 
and 
,
some graph 
contains a 
minor model whose branch sets are paths, and therefore has treewidth at least 
. At the same time, 
has no 
wall or 
as an induced minor, has girth at least 
, and places every two vertices of degree at least 4 at distance
at least 
.
Every induced subgraph of 
representable as the intersection graph of
curves in a half-plane, each with exactly one endpoint on its boundary, has treewidth
at most 
.
