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 and add an edge to connect ’s neighbor.
- Pendant/isolated vertex/loop reduction: Remove a vertex with degree at most , remove loops.
For an edge , a sequence of reduction is called -avoiding if none of the reduction delete or the vertices incident to .
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 .
A graph has treewidth , 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 -avoiding reduction reduce the graph to a single edge .
Every simple treewidth graph with at least vertices has at least non-adjacent vertices with degree at most , or it is a triangle.
Consider a tree decomposition. If it has more than bags, then there are leaves. In each leave, there exist a vertex with degree at most , since it is not incident to any vertex outside it’s bag and there are at most other vertices in the bag. Also, those two vertices are not adjacent to each other.
If it contain only bag, and if there is no non-adjacent vertices wit degree at most , then it must be a triangle.
A graph has treewidth 2 if and only if for every edge , every maximal sequence of -avoiding reduction reduce the graph to the edge .
For one direction, consider any -avoiding reduction that reduces the graph to a single edge . Apply two more vertex removal to get the empty graph.
For the other direction, assume incident to edge .
The proof is by induction. The base case where is a graph with at most vertices is trivial.
Consider the induction step with a graph with at least vertices. Each reduction operation can be expressed as minor operations, thus it results a treewidth graph, hence it has the desired property. Thus we need to show if a graph has treewidth , one of the operations can be applied. Indeed, we can always apply a reduction if there is at least 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 , otherwise one of them is not or and can be removed with series reduction. If the graph is a triangle, then there is a vertex with degree that’s not and . Hence, by the Lemma, the graph can have at most vertices. ::: Remark One can apply this to show that the AB-reducible graphs and generalized outerplanar graphs in [1] is exactly the graphs with treewidth .
Acknowledgment
I wish to thank Urvashi Khandelwal and Vivek Madan for helpful discussions.