On Subgraph Sizes in Random Graphs
Neil J. Calkin, ALAN M. FRIEZE, Brendan D. McKay · Combinatorics Probability Computing · 1992
For a graph G with m edges let its Range of Subgraph Sizes (RSS) ρ(G) = {t : G contains a vertex-induced subgraph with t edges}. G has a full RSS if ρ(G) = {0, 1, …, m}. We establish the threshold for a random graph to have a full RSS and give tight bounds on the likely RSS of a dense random graph.