Cayley's Theorem regarding marked trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:49:00Z http://mathoverflow.net/feeds/question/75878 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75878/cayleys-theorem-regarding-marked-trees Cayley's Theorem regarding marked trees unknown (google) 2011-09-19T17:51:31Z 2011-09-19T19:22:44Z <p>Hello,</p> <p>I have the following proof of Cayley's Theorem: <a href="http://imageshack.us/photo/my-images/821/sformulaproof.png" rel="nofollow">Proof</a>.</p> <p>This proof counts orderings of directed edges of rooted trees in two ways and concludes the number of rooted trees with directed edges of order \$n\$.</p> <p>However, I know a version of Cayley's Theorem in which \$n^{n-2}\$ is the number of marked trees spanning \$K_{n}\$.</p> <p>What I need is to show that the number of marked trees spanning \$K_{n}\$ is equal to the number of rooted trees with directed edges of order \$n\$. This way, the proof given above will be valid for the version I know of the theorem.</p> <p>As I understand, rooted trees and rooted trees with directed edges are the same thing. It shouldn't be hard to prove anyway. The rest, I don't know.</p> <p>Thanks.</p> http://mathoverflow.net/questions/75878/cayleys-theorem-regarding-marked-trees/75882#75882 Answer by Aaron Meyerowitz for Cayley's Theorem regarding marked trees Aaron Meyerowitz 2011-09-19T19:22:44Z 2011-09-19T19:22:44Z <p>What is the question? This proof is in "Proofs from the Book" and credited to Jim Pitman.</p>