Abstract
We formalize tree decompositions and tree width in Isabelle/HOL,
proving that trees have treewidth 1. We also show that every edge of
a tree decomposition is a separation of the underlying graph. As an
application of this theorem we prove that complete graphs of size n
have treewidth n-1.