Searching for an edge in a graph

Consider the problem of determining the endpoints of an unknown edge x in a given graph G by asking questions of the form “Is vertex v an endpoint of edge e in G?”. Sharp upper and lower bounds are derived, and it is shown that determining the minimum number of questions in NP-complete.