Strongly balanced graphs and random graphs

Abstract

Abstract The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with v vertices and e edges if and only if I ν – 1 ⩽ e ⩽( ). This result is applied to a classic question of Erdös and Rényi: What is the probability that a random graph on n vertices contains a given graph? A rooted version of this problem is also solved.