Let G=(V,E) be a graph and &etilde;∈E an unknown edge. In order to find &etilde; a sequence of test sets WℝV is chosen, where information is given after every test whether both vertices incident to &etilde; are in W, or not. For c(G), the minimum number of tests required, the inequality c(G)∈⌈log2∈E∈⌉ clearly holds (information theoretic lower bound). It was conjectured by Chang and Hwang that for a bipartite graph G this lower bound is always achieved. Here it is shown that c(G)∈⌈log2∈E∈⌉+1 for bipartite graphs and c(G)∈⌈log2∈E∈⌉+3 for arbitrary graphs.
