Can we say in general, Treewidth of every graph is less than or equal to number of vertices in that graph? Is there any other general relation between Treewidth and Order of graphs?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The treewidth of an $n$-vertex graph is always at most $n-1$ (because it is defined as one less than the cardinality of the largest bag in an optimal tree decomposition, and each bag is a set of $n$ or fewer vertices). It is exactly $n-1$ in the case of a complete graph, and can be as small as $0$ for an independent set, so there is no tighter relation possible between treewidth and $n$.
answered Dec 15, 2015 at 0:35