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

6

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.