  In this paper, we give a very simple proof that Treewidth is NP-complete;
this proof also shows NP-completeness on the class of co-bipartite graphs. We
then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is
NP-complete on graphs with maximum degree at most 9, by showing that Treewidth
is NP-complete on cubic graphs.
