Testing subgraphs in large graphs

Let H be a fixed graph with h vertices, let G be a graph on it vertices, and suppose that at least epsilonn(2) edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f(epsilon, H)n(h) copies of H. We show that the largest possible function f(epsilon, H) is polynornial in E if and only if H is bipartite. This implies that there is a one-sided error property tester for checking H-freeness, whose query complexity is polynomial in 1/epsilon, if and only if H is bipartite. (C) 2002 Wiley Periodicals, Inc.