Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Thank you for your answer. I am just wondering, in order to get a minor I need to apply edge contraction on two vertices of the graph, and after that replace these two by new one –  com Jan 14 '12 at 16:09
    
@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? –  Ali Amiri Jan 14 '12 at 16:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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