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 a graph 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 k-tree, while
a graph with treewidth 
are known as partial k-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 graph minor,
has girth at least 
, and places every two vertices
with vertex 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 
.
For a fixed planar graph 
,
let 
be the least upper bound on the treewidth
of graphs excluding 
as a graph minor. If 
is a disjoint graph union of
cycle graphs and 
,
Hatzel et al. (2026) prove
 |
(10)
|
where 
denotes big-O
notation. More precisely, if 
is a disjoint union of 
cycle graphs of length at most
, then an absolute constant 
satisfies
 |
(11)
|
This improves the general planar-exclusion bound for this family of forbidden graph minors.
