#####
Séminaire Lotharingien de Combinatoire, B15h (1986).

[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-15, p.
101-104.]

# Eberhard Triesch

# Kantensuche in Graphen

**Abstract.**
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 the problem of determining the
minimum number of questions is NP-complete.

The paper has been finally published as a joint paper with Martin Aigner
under the title
"Searching for an edge in a graph" in
*J. Graph Theory* **12** (1988), 45-57.