2
$\begingroup$

I try to prove that,

For any integer $k$, the graphs with treewidth at most $k$ define a minor-closed family.

At first the idea of the proof doesn't seem to be complicated.

Let's say we have a graph $G$ with treewidth $k$ and graph's tree decomposition $T$. Let's apply edge contraction to the edge $uv$ in the graph $G$. The vertices $w$ we get by merging $u$ and $v$. Obviously, we've changed the structure of the graph, as well as the structure of it's minor(very awkward conclusion, can be improved?). Have changed the structure of the graph, we should modify the tree decomposition $T$ by replacing every occurrence of $uv$ by $w$(also not strong sentence, the treewidth might have changed and might not).

Unfortunately, I have a problem with formulation of this proof, it looks like, at least for me, that idea behind the proof is very clear. Please, can you help me, to show me my mistakes.

Thanks!

Addendum: I just want to add few thoughts about the proof. Let's rephrase the statement, treewidth of the minor of the graph $G$ cannot be greater than treewidth of $G$. But, by edge contraction we can either make the treewidth smaller or don't change it at all. Therefore, it looks like we really have a closed family of graph with treewidth at most $k$.

2 Answers 2

2

Currently I can't push the comment So I write it as answer, hope helps, but assume you have a nice tree decomposition such that there is no node t^*\in T \space such \space that\space t^*\subseteq t' now you can pick one of a leaf of Tree, and you know this node has some vertex $w$ in it such that there is no other node $t \in T$ such that it has $w$ so you can run your edge contraction on $w$ and there is no change in size of tree decomposition.

  • 0
    @com I don't know is that help you or not?but I just suggest to don't select arbitrary nodes for contraction.also if the proof you read uses arbitrary vertices would you reference to paper?2012-01-14