HUNGARIAN ACADEMY OF SCIENCES

We shall prove that if L is a 3-chromatic (so called "forbidden") graph, and-R " is a random graph on n vertices, whose edges are chosen indepen--6 " is a bipartite subgraph of R " of maximum size,-F " is an L-free subgraph of R " of maximum size, dently, with probability p, and then (in some sense) F " and 6 " are very near to each other: almost surely they have almost the same number of edges, and one can delete O, ( 1) edges from F " to obtain a bipartite graph. Moreover, with p = and L any odd cycle, F " is almost surely bipartite. Notation. Below we restrict our consideration to simple graphs: loops and multiple edges are excluded. We shall denote the number of edges of a graph G by e(G), the number of vertices by u(G), but superscripts will also denote the number of vertices; G", R", T"*d will always be graphs on n ver-tices. The set of vertices of a graph G is denoted by V(G). The subgraph of a graph F spanned by a subset A will be denoted by GF(A), or simply by G(A). The chromatic number of a graph G will be denoted by x(G). The number of edges of a graph will be called "the size of the graph. " If X and Yare disjoint vertex sets in a graph G, then ec(X, Y) denotes the number of edges joining X to Y, and dc(X, Y) denotes the edge-density between them