Results 1 to 4 of 4

Math Help - Graph Theory.

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Graph Theory - Unlabeled Trees

    Hello MHF -

    I don't want to see like I'm relying on this forum for HW, so let me qualify this question. If you don't need the qualification, skip on down to the question. I am currently taking Graph Theory and struggling with it. My professor has an annoying (though thoroughly entertaining) tendency to throw interesting theorems at the class. It's been ~10 lectures and we are having our first quiz on Thursday. The following problem is from a 'practice' quiz we took on Monday and, due to the ad hoc nature of the teaching, I don't even know where to begin to start looking for the answer.

    Question: Show that the number of non-isomorphic unlabeled trees on n vertices is >= (n^(n-2)) / n! [which converges to e^n]

    My attempt to answer: I started by proving that there are n^(n-2) labeled trees for n vertices since the Prufer Code would contain n-2 entries, and each entry could be any of the n vertices; Since each ordered set of numbers gives a distinct labeled tree, n^(n-2) trees.

    But how do I get the n! in the denominator?
    Last edited by jsndacruz; October 19th 2011 at 01:15 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    Posts
    23

    Re: Graph Theory.

    Two graphs are isomorphic if there is a permutation of the vertices that takes one to the other. How many permutations on n vertices are there? Would dividing by this number not be a lower bound for the number of non-isomorphic ones?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Graph Theory.

    Thanks zerodivisor. I just realized that - was going to report back but you beat me to it. I haven't taken any combinatorics classes so I just have to get into the habit of thinking about permutations and such.

    The second part of the question: show that an upper bound being 4^n. We were given a hint which showed a tree and traced a path along the entire (you could traverse each edge twice; I don't think it matters how many times you cross a vertex)

    My thoughts so far: each point within a graph is connected by a unique path. I'll keep thinking about it and post back.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Graph Theory.

    Ok so there are two ways that I've figured out an upper bound on the number of unlabeled trees with n vertices being < (4^n)

    Method 1: This was explained in another text I found. Imagine that the tree's vertices can be traversed only twice and you had to cover the entire graph. There are (n-1) edges. Use any arbitrary vertex as your starting point. Each time you cross an edge, you are either going towards or away from that starting point (measured by # of vertices between yourself and the starting point). Since there are 2 choices for the 2(n-1) you travel across an edge, there are at the most 2^(2(n-1)) = 4^(n-1) < (4^n) ways of covering the graph.

    Method 2: This was my method, which is just as ugly as the method above. At any vertex you have 4 choices for how to 'move.' Either progress forward (as in a path), branch right, branch left, or turn around (vertex is a leaf). Since there are n vertices, and 4 choices each time, you have at most 4^n ways of constructing such a graph. Some of them will inevitably be isomorphic, so there will be less.

    I understand neither of the methods are in math-speak, but for now they will suffice. Unless I'm completely wrong.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum