Edge search in graphs with restricted test sets

We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for cp(G). For the case that G is the complete graph Kn 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 cp of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.