EXTREMAL SUBGRAPHS OF RANDOM GRAPHS

We shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and —Rn is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bn is a bipartite subgraph of Rn of maximum size, —Fn is an L‐free subgraph of Rn of maximum size, then (in some sense) Fn and Bn are very near to each other: almost surely they have almost the same number of edges, and one can delete Op(1) edges from Fn to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fn is almost surely bipartite. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company