(English translation of the original article, by Gemini 3 Pro (~90%) + me.)

This article is for the 21st day of Tree Advent Calendar 2025.

Overview

For a graph $G$, let $\mathrm{tw}(G)$ denote the treewidth of $G$.

This article introduces a simple algorithm to solve the following decision problem.

Input: A (simple undirected) graph $G = (V, E)$ with $n$ vertices and $m$ edges.
Output: Is $\mathrm{tw}(G) \leq 3$?

Expert readers might know these facts:

  • For any $k$, determining if the treewidth is at most $k$ can be solved in $O(f(k) \cdot n)$ time (☆).
  • It suffices to check a finite number of forbidden minors for treewidth at most $3$, which can be done in $O(n^{1+o(1)})$ time (☆) (★).

The algorithm introduced in this article is not one of those “strong” ones, but a human-friendly algorithm that allows you to easily determine with pen and paper if the treewidth is at most $3$ when a graph is given. It is an algorithm by [Arnborg & Proskurowski, 1986].

As this article is niche, I assume the reader is somewhat familiar with the concept of treewidth. If not, I recommend slides by Yoshio Okamoto. (Note: they are in Japanese)

Preparation

Treewidth and Tree Decomposition

A tree decomposition $\mathcal{T}$ of a graph $G = (V, E)$ is a pair of a tree $T$ and a family of vertex sets $\mathcal{X} = \{X_t \subseteq V \mid t \in V(T) \}$ that satisfies all of the following conditions:

  • $\bigcup_{t \in V(T)} X_t = V$.
  • For every edge $\{u, v\} \in E$, there exists some $t \in V(T)$ such that $\{u, v\} \subseteq X_t$.
  • For every vertex $u \in V$, the set of vertices $V_u = \{t \in V(T) \mid u \in X_t\}$ induces a connected subtree of $T$.

(Informally) In this article, we call each vertex $t$ of the tree $T$ a bag, and express $X_t$ as its contents.

The width of a tree decomposition $\mathcal{T}$ is defined as the maximum size of a bag minus one, i.e., $\max\{|X_t| \mid t \in V(T) \} - 1$. The treewidth $\mathrm{tw}(G)$ of $G$ is the minimum width over all possible tree decompositions of $G$.

Properties of Treewidth and Tree Decomposition

The following are known for any graph $G$. These are folklore, so you should be able to find proofs on the internet.

Property 1
The treewidth of a graph $G$ is equal to the maximum treewidth of its connected components. That is, if the connected components of $G$ are $C_1, \dots, C_t$, then $\mathrm{tw}(G) = \max_{1 \leq i \leq t} \mathrm{tw}(C_i)$ holds.
Property 2
If $H$ is a graph obtained from graph $G$ by minor operations (vertex deletion, edge deletion, edge contraction), then $\mathrm{tw}(H) \leq \mathrm{tw}(G)$.
Property 3
Graph $G$ has a vertex of degree at most $\mathrm{tw}(G)$.
Property 4
Let vertex set $K \subseteq V(G)$ be a clique in $G$. Then, in any tree decomposition, there exists a bag that contains $K$ as a subset.

Algorithm

I will give algorithms to determine “Is treewidth at most 1?” up to “Is treewidth at most 3?” in order. Using these, it is possible to determine not only $\mathrm{tw}(G) \leq 3$ but also whether $\mathrm{tw}(G) = 3$.

Also, from Property 1, we assume that the given graph $G$ is connected. To avoid corner cases, we also assume that $n$ is sufficiently large (about $n > 5$).

Is treewidth at most 1 ?

Since treewidth $\leq 1 \Leftrightarrow$ it is a forest, this can be easily determined, but as practice, I will give an algorithm without using this fact. (Note that if there are no edges, the treewidth is $0$, so be careful with “$\leq 1$”.)

First, consider the case where there are no vertices of degree $1$ or less in the given graph $G$. From Property 3, this means $\mathrm{tw}(G) > 1$, so we can immediately return No.

Therefore, let’s assume a vertex $u \in V$ with degree $1$ or less. From the connectivity, the degree is actually exactly $1$. In fact, in this case, it can be shown that the deletion of $u$ is safe. That is, if $G'$ is the graph obtained by deleting $u$ (and the edge incident to $u$) from $G$, then $\mathrm{tw}(G') \leq 1 \implies \mathrm{tw}(G) \leq 1$ holds. Since the converse $\mathrm{tw}(G) \leq 1 \implies \mathrm{tw}(G') \leq 1$ holds from Property 2, we just need to recursively determine if $\mathrm{tw}(G') \leq 1$.

Finally, let’s confirm that $\mathrm{tw}(G') \leq 1 \implies \mathrm{tw}(G) \leq 1$. Take an arbitrary tree decomposition $\mathcal{T}$ of $G'$ with width $1$ or less. Let $v$ be the (unique) vertex adjacent to $u$ in graph $G$. At this time, take a bag containing $v$ from $\mathcal{T}$, and by adding a new bag to $\mathcal{T}$ as follows, we can obtain a tree decomposition of $G$ with width $1$.

Therefore, $\mathrm{tw}(G') \leq 1 \implies \mathrm{tw}(G) \leq 1$ holds.

Is treewidth at most 2?

The algorithm for determining “Is treewidth at most 1?” described above is simply the following flow:

  • Minimum degree $= 1$ $\rightarrow$ Delete that vertex and solve recursively.
  • Minimum degree $\geq 2$ $\rightarrow$ Return No.

In fact, “Is treewidth at most 2?” can be solved similarly.

  • Minimum degree $= 1$ $\rightarrow$ Delete that vertex and solve recursively. (safe for treewidth $\leq 2$ determination as well)
  • Minimum degree $= 2$ $\rightarrow$ I will explain this part.
  • Minimum degree $\geq 3$ $\rightarrow$ Return No.

Let’s assume a vertex $u \in V$ of degree $2$. Also, let $v, w$ be the two neighbors of $u$. In this case, it is safe to delete $u$ and add an edge between $v, w$ (if it doesn’t exist). Thus, it is possible to solve recursively in the same way.

Since this operation is equivalent to contracting the edge $\{u, v\}$, from Property 2 $\mathrm{tw}(G) \leq 2 \implies \mathrm{tw}(G') \leq 2$ follows, where $G'$ denotes the graph after the operation. Therefore, we just need to show the converse, $\mathrm{tw}(G') \leq 2 \implies \mathrm{tw}(G) \leq 2$.

The important point in this operation is that we made the vertex set $\{v, w\}$ a clique in $G'$. This forces any tree decomposition of $G'$ to have a bag containing $\{v, w\}$ as a subset (from Property 4). Take an arbitrary tree decomposition $\mathcal{T}$ of $G'$ with width $2$ or less, and take an arbitrary bag containing $\{v, w\}$ as a subset from $\mathcal{T}$. We can similarly obtain a tree decomposition of $G$ with width $2$ by adding a new bag to $\mathcal{T}$ as follows.

Therefore, $\mathrm{tw}(G') \leq 2 \implies \mathrm{tw}(G) \leq 2$ holds.

Is treewidth at most 3?

For treewidth $3$, the algorithm is again similar.

  • Minimum degree $= 1$ $\rightarrow$ Delete that vertex and solve recursively. (Safe for treewidth $\leq 3$ determination as well)
  • Minimum degree $= 2$ $\rightarrow$ Make the neighbors of the degree $2$ vertex a clique and solve recursively. (Safe)
  • Minimum degree $= 3$ $\rightarrow$ I will explain this part.
  • Minimum degree $\geq 4$ $\rightarrow$ Return No.

However, from degree $3$, the operation similar to degree $2$ is no longer safe. Namely, for a vertex $u$ of degree $3$, the operation – making $N(u)$ a clique and deleting $u$ – is not generally safe. Obtaining a tree decomposition of width $3$ or less of $G$ from that of $G'$, is possible by finding a bag containing $N(u)$ and attaching a bag of $u \cup N(u)$. The problem is that making $N(u)$ a clique may increase the treewidth from $3$ or less, to $4$ or more. The figure below is an example. The graph on the left has treewidth $3$, but the graph on the right has treewidth $4$.

However, in the case of degree $3$, it can be shown that such unsafe cases are only when vertices in $N(u)$ are not adjacent to each other.

Lemma 1
For a vertex $u \in V$ of degree $3$, if some $2$ vertices $v, w \in N(u)$ are adjacent, then the operation of making $N(u)$ a clique and deleting $u$ is safe (for treewidth $\leq 3$ determination).

This is because if we let $x$ be the unique vertex contained in the vertex set $N(u) \setminus \{v, w\}$, we can observe that the graph obtained by contracting the edge $\{u, x\}$ is $G'$, and from Property 2, the treewidth does not increase.

If we solve recursively as long as there are such “safe” vertices of degree $3$, what remains is the case where:

  • The minimum degree is $3$, and
  • For every vertex $u$ of degree $3$, the vertices in $N(u)$ are not adjacent to each other.

One of the contributions of [Arnborg & Proskurowski, 1986] is the following theorem.

Theorem 3.2 [Arnborg & Proskurowski, 1986]
Suppose a graph $G$ satisfies the above two conditions and its treewidth is at most $3$. Then, graph $G$ contains a subgraph isomorphic to $C'$ or $C''$ in the figure below such that the vertices corresponding to $u_1, u_2, u_3, x$ in the figure have degree $3$.

Even with a naïve approach, we can find such a subgraph in $O(n^3)$ time (if it exists). If it does not exist, we can determine No. Another contribution of them is that if there is such a subgraph, the vertices corresponding to $u_1, u_2, u_3$ are “safe” vertices.

Theorem 3.3 [Arnborg & Proskurowski, 1986]
Suppose that $\mathrm{tw}(G) \leq 3$ and $G$ contains a subgraph isomorphic to $C'$ or $C''$ in the figure such that the vertices corresponding to $u_1, u_2, u_3$ in the figure have degree $3$. Then, for each $u \in \{u_1, u_2, u_3\}$, the operation of making $N(u)$ a clique and deleting $u$" is safe.

Therefore, even when the minimum degree is $3$, we can always find a “safe” vertex $u$ in $O(n^3)$ time with a simple algorithm, and solve recursively by making its neighborhood $N(u)$ a clique.

Extras

Is treewidth at most 4?

There is a paper with the same flavor.

Are there graph classes where treewidth is upper-bounded by 3, not 2?

I don’t know much. Outerplanar graphs and series-parallel graphs are known to have treewidth at most $2$. Outer 1-planar graphs have treewidth at most $3$. Halin Graphs have treewidth exactly $3$.

It appears that planar $\cap$ 3-tree, namely, the class of planar and maximal treewidth-$3$ graphs, is well studied as Apollonian network.