For each pair of nonadjacent vertices in a graph, consider the greater
of the degrees of the two vertices. The minimum of these maxima is a
lower bound on the treewidth of a graph, unless it is a complete graph
. This bound has three consequences. First, the obstructions of order
w + 3 for treewidth w have a simple structural characterization, Secon
d, these graphs are exactly the pathwidth obstructions of order w + 3.
Finally, although there is only one obstruction of order w + 2 for wi
dth w, the number of obstructions of order w + 3 is bounded below by a
n exponential function of root w.