からへの単純パスの本数をと表すことにします．
のとき， 鳩ノ巣原理より条件を満たすパスの組が必ず存在することが言えます．
よってこれ以降はとします．
次にをを用いて実際に表すと以下の式となります．
今であるのでこれを変形して，
を得ます．
また，制約よりであるので，
です．
この不等式を満たすようなは高々であることが実際の計算により確かめることができます．
であるので，実際にあり得るパスをすべて列挙し， 長さが同じであるものが存在するかどうかを見ればよいです．
時間計算量は上で表したを用いてです． 厳密にはもっと厳しい評価や，実装の際の枝刈りができるため， 実際の計算回数はもう少し少なく抑えることができます．