3
$\begingroup$

Is the treewidth of this graph equal to 2?

K4 with C6 with two pendants

I have tried to prove it through the definition of a tree decomposition.

If its not correct can someone give any hints?

$\endgroup$
3
$\begingroup$

In the survey Treewidth, partial $k$-trees, and chordal graphs by Pinar Heggernes, we have the following lemma, whose proof is given as an exercise.

Lemma. Let $(\{X_i \mid i \in I\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$. Then there exists an $i \in I$ with $K \subseteq X_i$.

Prove this lemma, and conclude that, as Yuval answered,

Corollary. For every graph $G$, $tw(G) \geq \omega(G) - 1$.

Conclude that the treewidth is at least three.

The treewidth happens to be at most three as well, but that's a different exercise.

$\endgroup$
2
$\begingroup$

Treewidth is always at least the clique number minus one. Your graph has a $K_4$, so its treewidth is at least 3.

$\endgroup$
2
$\begingroup$

The class of graphs of treewidth two is precisely the class of graphs that are $K_4$-minor-free. Because your graph contains a $K_4$-minor, it has treewidth different from two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.