A group testing problem for graphs with several defective edges Original Research Article

In their book on group testing Du and Hwang (Combinatorial Group testing and its Applications, World Scientific, Singapore, 1993) considered the following generalization of classical group testing problems: Suppose a graph contains m edges d of which are defective. Find all defective edges by testing whether an induced subgraph contains a defective edge or not. They conjectured that this can be done by using at mostdlog2 md+ctests for some constant c. We prove this conjecture for c=7.