Results 1 to 1 of 1

Math Help - Trees, subtrees and isomorphisms

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    4

    Trees, subtrees and isomorphisms

    Hi,

    the following question came to my mind. Let a tree T be a directed graph with a distinguished root node r, such that there exists a unique path from r to each node v. Moreover, let T(n) denote the subgraph induced by the nodes of depth <=n.

    My conjecture:
    For any two trees T and T', if T(n) and T'(n) are isomorphic for each n, then T and T' are isomorphic as well.

    This appears entirely obvious, but I only found a proof for finitely branching trees.

    In general, it seems promising to build up a sequence of isomorphisms f_n:T(n)->T'(n) such that f_(n+1) extends f_n for each n. Then the f_n could be extended to an isomorphism of T and T'. But how do I find the f_n?

    Any ideas?

    Greetings
    proxximus
    Last edited by proxximus; September 16th 2009 at 02:12 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 20th 2011, 03:14 PM
  2. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: May 23rd 2009, 07:05 PM
  3. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 12:43 PM
  4. Z2 + Z2 + Z3 isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 2nd 2008, 07:34 PM
  5. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 28th 2006, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum