Thread: Graph Theory.

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?

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?

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.

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.