4
$\begingroup$

It is well known that the finite rooted trees are well-quasi-ordered by the topological minor relation (a.k.a. homeomorphic embedding). Are they also wqo by the (induced) subgraph relation?

I'm confused because it seems to me that Nash-Williams proof can easily be adapted to induced subgraphs. This would be a stronger (and simpler) result.

Does anyone know a bad sequence?

1 Answers 1

7

Consider the rooted trees shown below (with root at the top):

   *          *          *          *          *          *      |\         |\         |\         |\         |\         |\      * *        * *        * *        * *        * *        * *            |\         |          |          |          |          |              * *        *          *          *          *          *                         |\         |          |          |          |                         * *        *          *          *          *                             |\         |          |          |   ...                          * *        *          *          *                                       |\         |          |                                       * *        *          *                                                  |\         |                                                  * *        *                                                             |\                                                             * * 

Clearly none of them is an induced subgraph of another, so this is an infinite antichain in the induced subgraph ordering of finite rooted trees, which is therefore not a well-quasi-order.