命題2.4： 始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする 有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から 頂点 v への最短路となっている。
証明： 始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。 定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、 これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、 以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。 T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には v_* に向かう枝が2つ以上ある。 …
v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？
証明： T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。 仮に、上の v_* が存在しないと仮定する。 v を上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、 仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた とき、有向閉路である。 T の作り方から s に向かう枝は存在しないから、 s はこの有向閉路上にはない。
T の作り方から、 s から v への有向路が存在する。 この有向路上の頂点で最初に上の有向閉路上の頂点ともなる頂点を w とする。 上の有向路上で w の直前の頂点を u とする。 w は上の有向閉路上の頂点であるから、 w へ向かう 上の有向閉路上の枝が存在する。 u は w についての仮定から、上の有向閉路上の頂点ではない。 以上から、 w へ向かう少なくとも2つ以上の枝が存在することになる。 これは矛盾である。
