公式解説で示されている重要な事実(深さ $d+1$ の部屋には、深さ $d$ の部屋が $1$ つ以上繋がっている)を証明します。
証明には背理法を用います。

深さ $d+1$ の部屋( $X$ とします)と深さが $d-1$ 以下の部屋( $Y$ とします)が繋がっている場合

この場合、 $X$ から $Y$ に行き、そこからその部屋から最短で部屋 $1$ に移動すれば移動回数は $d-1+1 = d$ 以下になります。
よって部屋 $X$ の深さは $d$ 以下になるので、矛盾です。

よって、 $X$ に繋がっている部屋の深さは全て $d$ 以上です。( ① とします)

深さ $d+1$ の部屋( $X$ とします)に繋がっている部屋の深さが全て $d+1$ 以上の場合

$X$ の深さは $1$ 以上なので、部屋 $1$ に向かうには $X$ と繋がっている部屋を通る必要があります。
ここで、 $X$ と繋がっている部屋のどれを選んでも、そこからその部屋から最短で部屋 $1$ に移動した場合の移動回数は $d+1+1 = d+2$ 以上になります。
よって部屋 $X$ の深さは $d+2$ 以上になるので、矛盾です。

よって、 $X$ に繋がっている部屋で、深さが $d$ 以下であるものが存在します。( ② とします)

①,② より示すことができました。