Lawrence (abangaku) wrote in moppers,

  • Mood:
  • Music:

"correct the night's mistakes" -- captain beefheart

so do you think someone could look over this proof i just came up with of a famous graph theory theorem (i don't remember its name)? one, is it accurate and two, if it is accurate, is it a famous proof?

To prove: For n > 0, there are n^(n-2) trees on n distinguishable vertices.

Number the set S of n vertices 0, 1, ..., n-1. In each tree, we can denote, without loss of generality, the vertex 0 to be a root vertex. The statement, then, is equivalent to proving that there are n^(n-2) rooted trees on vertices 0, 1, ..., n-1 with vertex 0 at the root. To enhance clarity, we visualize this set of trees as digraphs of out-degree 1 (except for the root), in which each vertex points towards its parent. Now, for each of these trees rooted in 0, we can mark one of the n points; if we can prove that there are n^(n-1) distinct "marked rooted trees" with root at 0, this is equivalent to the original problem.

We examine the class of all functions f: S\0 -> S in which each of the vertices in S, other than the root 0, is mapped to any of the vertices in S, including possibly itself (or 0). There are clearly n^(n-1) of these functions. I claim that there exists a one-to-one correspondence between these functions and the marked rooted trees defined above.

For each function f, we can construct a digraph G among the n points that connects each point k (0 < k < n) to f(k). Since f is defined on n-1 points, this is a digraph containing n-1 edeges and n vertices, with out-degree 1 except at 0. Call this f's digraph representation. Iterating f on any vertex k will lead eventually to either a termination at 0, or a loop. In fact, we can say that G consists of certainly one disconnected piece, containing 0, and also, perhaps any number (0 to n-1) of other disconnected pieces, terminating in loops, possibly with trees sprouting out of any of the points on a loop as a root. Indeed, there is a clear one-to-one correspondence between such digraph representations and functions f.

Now, the set of all possible digraph representations contains within it the set of trees on the n points rooted at 0, expressed as digraphs described above, but (for n>1) is also larger than it, as it contains digraphs with loops. For each of these representations, we create a marked rooted tree by splicing the loops together in the following way: In each of the loops (not the pieces containing the loops, but the loops themselves), select the largest-numbered vertex and delete the edge coming out of it; stick some "glue" onto the vertex that was at the other end of this edge. Now, order the former loop-containing pieces by the size of their largest-numbered vertices, largest to smallest, and connect each largest-numbered loop number to the "gluey" vertex in the next piece. The last largest-numbered loop number will be connected to the root, as there is no next piece. The "gluey" vertex on the first piece becomes the marked vertex of the marked rooted tree this has just turned into. (The root vertex 0 gets marked, with no further changes, when there were no loops to begin with, as in this case we have already a rooted tree.) All trees sprouting out of vertices formerly on loops are left unchanged.

The inverse procedure, to turn a marked rooted tree into a digraph representation, is as follows. Examine the line of vertices comprised of the marked vertex and all its ancestors (including the edges between them), back to the root. Reading this sequence from the root 0 towards the marked vertex, we note each time we encounter a vertex with a larger number than any on this sequence we have encountered before, and delete the edge leading to it. We have now divided this line into segments (possibly only one piece, if 0 was the marked vertex), again with perhaps trees sprouting out of the vertices on each segment. Now connect the first vertex in each segment to the last vertex in that segment, rather than the last vertex in the previous segment; clearly, these first vertices will have the highest numbers in their segment, which now becomes their loop. Since every vertex but 0 now has out-degree 1 again, we have a digraph representation indeed. It is comprised of a piece including 0, and a set of loops such that what was the marked vertex immediately follows the largest-numbered vertex contained in any of the loops. (If this vertex is the marked vertex, then the marked vertex points to itself.) Therefore, we will surely get the original marked rooted tree back when we apply the procedure in the paragraph above, as the highest-numbered vertices of each loop are the same as the successively higher-numbered vertices we counted out along the marked vertex's ancestors. To see that all digraph representations can be generated in this way, we use the first procedure to transform each one into a tree and then turn it back, using this procedure, into a digraph representation; again, since by the ordering we did of the representation's loops in the first procedure, the highest-numbered vertex in each loop gets progressively higher as we recede from the root, and thus these become the successively higher-numbered vertices in the trip from 0 to the marked vertex, we see that we get the same digraph representation back.

The two procedures are therefore inverses of each other, and so as there are n^(n-1) digraph representations of functions f, there are n^(n-1) marked rooted trees on the n vertices rooted at 0, and so, by the first paragraph, there are indeed n^(n-2) unrooted, undirected graphs on the n (distinguishable) vertices -- 1^(-1) = 1 on 1 vertex, 2^0 = 1 on 2 vertices, 3^1 = 3 on 3 vertices, 4^2 = 16 on 4 vertices, 5^3 = 125 on 5 vertices, 6^4 = 1296 on 6 vertices, and so on.
  • Post a new comment


    default userpic
  • 1 comment