Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.