A characterization of treewidth 2 graphs
Consider 3 reduction operations on a graph:
- Parallel reduction: Remove an parallel edge.
- Series reduction: Remove a degree 2 vertex v and add an edge to connect v's neighbor.
- 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.
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.
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.
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.
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 (Cheng et al., 2012) is exactly the graphs with treewidth 2. :::