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.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.