Skip to main content

New answers tagged

7 votes

What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

The smallest such example that is known to the House of Graphs is for $k = 9$. There is a graph of tree-width $9$ having only $44$ edges (while the $10$-clique contains $45$ edges).
tomil's user avatar
  • 71

Top 50 recent answers are included