Definition 2: If we replace the edges of X with independent paths between their ends (so that none of these paths has an inner vertex on another path or in X), we call the graph G obtained "a subdivision of X" and write "G = TX". If G=TX is the subgraph of another graph Y, then X is "a topological minor of Y".

Problem: show that, if Δ(X) ≤ 3, then every MX contains a TX; thus, every minor with maximum degree at most 3 of a graph is also its topological minor.

in one brance set, there is at most three node which connects other three different branch set(since \triangle(X)<=3.),call this three node output
pick a path connects two output, and pick an other path connect the 3rd output to the previous path. the intersecting node is brance node.

retaining these paths and edges between brance set leaves a TX.

PS: Yes, I am reading Reinhard's book. It's really great (though some contents are a little bit too much for me......).

以下是引用ljb在2005-3-20 22:00:08的发言： such a easy problem~~~ the only thing you need to do is to find a brance node in one brance set in one brance set, there is at most three node which connects other three different branch set(since \triangle(X)<=3.),call this three node output pick a path connects two output, and pick an other path connect the 3rd output to the previous path. the intersecting node is brance node. retaining these paths and edges between brance set leaves a TX.

以下是引用ljb在2000-1-1 9:12:08的发言： ~~~~~~~ some content are not that useful for CSer,such as "extremal graph theory and ramsey theory" I think,although they are really beautiful theory.