Infinite sequence of trees that are not subgraphs to each other

185 Views Asked by At

This is from a set of exercises and I am stuck to this. Please, have in mind, that I want to understand how it's solved, I am not just looking for a solution.

Define an infinite sequence of trees $T_1, T_2, T_3, ...$ (by drawing the first elements of the sequence), where, for any $i$ and $j$, with $i \neq j$, $T_i$ is not a subgraph of $T_j$. We can see that the set of trees is not well-quasi-ordered to the relation of the "subgraph".

My mind has made it to this stage: A tree is connected graph, with no cycles. A subgraph $H$ of $G$, is formed from $G$, by deleting vertices and edges (you may skip an operation (e.g. delete only vertices)). I thought starting with a tree with four nodes. Let $T_1$ be the tree with edges: $(1, 2) (2, 3) (3, 4)$ and $T_2$: $(1, 3) (1, 4) (2, 4)$ but then what?

1

There are 1 best solutions below

0
On BEST ANSWER

Based on the comments above by dtldarek, I will solve this assignment like this:

Ti will be two S6 (star graphs that have 6 outer nodes and one internal), joined by a path of length i.