In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph Kn,p.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics