In the graph reconstruction problem, we are given the vertex set \(V\)  of a hidden connected, undirected, and unweighted graph and have access to information about the topology of the graph via an oracle, and the goal is to find every edge in \(E\) .
Henceforth, unless explicitly mentioned, all graphs studied are assumed to be connected.
This assumption is standard and shared by almost all references on the subject, e.g., [1]}, [2]}, [3]}, [4]}, [5]}.
The efficiency of an algorithm is measured by the query complexity, i.e., the number of queries to the oracle.
Motivated by traceroute, the literature has explored several types of query oracles.
