 # A characterization of treewidth 2 graphs

Consider 3 reduction operations on a graph:

1. Parallel reduction: Remove an parallel edge.
2. Series reduction: Remove a degree 2 vertex $v$ and add an edge to connect $v$’s neighbor.
3. Pendant/isolated vertex/loop reduction: Remove a vertex with degree at most $1$, remove loops.

For an edge $e$, a sequence of reduction is called $e$-avoiding if none of the reduction delete $e$ or the vertices incident to $e$.

A reduction sequence is maximal if there is no reduction can be applied or any reduction will decrease the number of vertices to less than $2$.

A graph has treewidth $2$, if and only if there exist a reduction sequence that reduce the graph to an empty graph.

We can prove a stronger result, such that we can make sure that every maximal $e$-avoiding reduction reduce the graph to a single edge $e$.

Lemma1

Every simple treewidth $2$ graph $G$ with at least $3$ vertices has at least $2$ non-adjacent vertices with degree at most $2$, or it is a triangle.

Proof

Consider a tree decomposition. If it has more than $2$ bags, then there are $2$ leaves. In each leave, there exist a vertex with degree at most $2$, since it is not incident to any vertex outside it’s bag and there are at most $2$ other vertices in the bag. Also, those two vertices are not adjacent to each other.

If it contain only $1$ bag, and if there is no $2$ non-adjacent vertices wit degree at most $2$, then it must be a triangle.

Theorem2

A graph $G$ has treewidth 2 if and only if for every edge $e$, every maximal sequence of $e$-avoiding reduction reduce the graph to the edge $e$.

Proof

For one direction, consider any $e$-avoiding reduction that reduces the graph to a single edge $e$. Apply two more vertex removal to get the empty graph.

For the other direction, assume $e$ incident to edge $uv$.

The proof is by induction. The base case where $G$ is a graph with at most $2$ vertices is trivial.

Consider the induction step with a graph $G$ with at least $3$ vertices. Each reduction operation can be expressed as minor operations, thus it results a treewidth $2$ graph, hence it has the desired property. Thus we need to show if a graph has treewidth $2$, one of the operations can be applied. Indeed, we can always apply a reduction if there is at least $3$ vertices.

If none of the operations can be applied, then the graph has to be simple. There can’t be two non-adjacent vertices with degree at most $2$, otherwise one of them is not $u$ or $v$ and can be removed with series reduction. If the graph is a triangle, then there is a vertex with degree $2$ that’s not $u$ and $v$. Hence, by the Lemma, the graph can have at most $2$ vertices. ::: Remark One can apply this to show that the AB-reducible graphs and generalized outerplanar graphs in  is exactly the graphs with treewidth $2$.

# Acknowledgment

I wish to thank Urvashi Khandelwal and Vivek Madan for helpful discussions.

# References

 Q. Cheng, F. Chen, W. Xu, S. Wang, Recursive sum–product algorithm for generalized outer-planar graphs, Information Processing Letters. 112 (2012) 449–456 10.1016/j.ipl.2012.03.001.

Posted by Chao Xu on .
Tags: Graph theory.