Limited number of calls to a black box for finding longest path in graph given an access to oracle I'm given a black box that on graph $G = (V,E)$ and integer $0&lt; K&lt;|V|$ outputs $1$ iff there is a simple path of length greater than $K$ in $G$. I want to find the actual edges of the longest path in $G$ using as few calls to my black box as possible. 

What I've come up with thus far is using the same method as when binary searching, i.e. first calling my black box with $K = |V|/2$ and so forth, but I'm not really sure what to do once I've found the $K_{max}$.. I'd really want to go in and change the black box to output the actual edges but that's impossible.

Edit: So I can delete any edge $e_i$ from $G$ and see if my black box still returns 1 (once I've found the maximal length path) - if it still returns 1 i know $e_i$ isn't part of the longest path, and if it returns 0 I know $e_i$ is part of the longest path(s) and I append it to my data structure holding the longest path. But what should I do if there are several paths of the maximum length? It feels as if I will return all the edges of all the longest paths and not just one specific.
Since you can find the actual length of the longest path using binary search, in $\log |V|$ steps, I'll assume you have access to an oracle which tells you the length of the longest path. Given a graph $G$ lets denote the length of the longest path in $G$ by $L(G)$.

If you remove an edge after finding out that it does not affect the length of the longest path in $G$, then you avoid the issue of having to commit to some specific longest path. Suppose you keep iterating over the remaining edges, and for each remainning edge $(u,v)$ you check if
$L(G)=L\left(G\setminus\left\{(u,v)\right\}\right)$. If they are equal, remove $(u,v)$ from $E$ and return to the main loop. When there are no more edges to delete, $E$ consists of a longest path in $G$.

To prove this, let $\mathcal{P}$ be the set of longest paths in $G$. Note that in any iteration $i$ (each iteration consists of removing an edge which does not affect the longest path length), there exists some $P\in\mathcal{P}$ such that $P$ is a path in $G_i$. Using this observation, you can show that when there are no more edges to delete, your graph is a longest path.