Random trees in random graphs

E. A. Bender, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)


We show that a random labeled n-vertex graph almost surely contains isomorphic copies of almost all labeled n-vertex trees, in two senses. In the first sense, the probability of each edge occurring in the graph diminishes as n increases, and the set of trees referred to as “almost all” depends on the random graph. In the other sense, the probability of an edge occurring is fixed, and the relevant set of trees is predetermined. The same method applies to show that almost all labeled ra-tournaments contain isomorphic copies of almost all labeled oriented n-trees.

Original languageEnglish
Pages (from-to)314-320
Number of pages7
JournalProceedings of the American Mathematical Society
Issue number1
Publication statusPublished - 1988
Externally publishedYes

Cite this