\(D_i=d_{1,i}+d_{2,i}\) とします。\(i=3,\ldots,N\) に対してこの値を求めることは \(2(N-2)=2N-4\) 回の質問で可能です。

\(D_i\) の最小値は多くの場合 \(d_{1,2}\) に一致します。唯一の例外は \(d_{1,2}=1\) の場合(頂点 \(1,2\) の間に頂点が無い場合)で、この場合 \(D_i\) の最小値は \(3\) となります。この時点で \(D_i\) の最小値が \(3\) 以外の場合は \(d_{1,2}\) が分かります.

\(D_i\) の最小値が \(3\) であった場合に \(d_{1,2}\) が \(1\) か \(3\) かを判定する方法を考えます。\(d_{1,2}=3\) と仮定すると、\(D_i=3\) となる \(i\) はちょうど \(2\) 個です。よって、これに反する場合は \(d_{1,2}=1\) です。
\(D_i=3\) となる \(i\) がちょうど \(2\) 個の時、それらを \(x,y\) とします。\(d_{1,2}=1\) の場合は \(x,y\) はそれぞれ頂点 \(1\) または頂点 \(2\) に隣接していて、\(d_{1,2}=3\) の場合は \(x,y\) が隣接しています。このことから、\(d_{x,y}\) が \(2\) または \(3\) の場合は \(d_{1,2}=1\)、 \(1\) の場合は \(d_{1,2}=3\) と分かります。

以上より、高々 \(2N-3\) 回の質問で \(d_{1,2}\) が求められました。