D の各頂点 v に対して D が r から v への路を持つなら、r を始根 (from-root) と呼ぶ。始根は単に根 (root) とも呼ぶ。
r が始根であり、無向多重グラフ Dund が閉路を持たないとき、D は r を根とする有向木 (arborescence rooted from r) と呼ばれる。 [Dund は D の弧を無向辺にすることで得られる多重グラフを表す2。このとき平行辺は一つにまとめられない！]
もちろん終根 (to-root) と r を終根とする有向木 (arborescence rooted to r) の概念を考えることもできる。しかし、終根は弧の向きを反転させたグラフにおける始根なので、二つの概念を別々に考える必要はない。始根に関する性質を示せば、全ての弧の向きを反転させたグラフにおける終根の性質も示される。
証明の本筋に入る前に、記法を一つ定める: D の任意の弧 a に対して、D から弧 a を除去して得られるグラフを D∖a と表記する。[数学的に言えば
D∖a:=(V,A∖{a},ψ∣A∖{a})
と定める。]
それでは六つの命題を証明していこう。
[A1 ⟹ A4 の証明] 命題 A1 が成り立つと仮定する。このとき D は r を根とする有向木である。言い換えれば、r は D の始根であり、Dund は閉路を持たない。
各頂点 v∈V に対して、多重有向グラフ D に r から v への歩道が唯一つ存在すると示せばよい。r が D の始根なので、この歩道の存在は明らかである。よって後は唯一性を示す必要がある。
背理法で示す。r から v への異なる二つの歩道 u, v が存在するような頂点 v が存在すると仮定する。Dund は閉路を持たないのでループを持たず、従って多重有向グラフ D もループを持たない。よって D の任意の歩道は自動的に Dund のバックトラックフリー歩道となる (有向グラフの歩道に含まれる連続する弧が同一なら、その弧はループである)。よって D における歩道 u と v は Dund における二つのバックトラックフリー歩道でもある。言い換えれば、Dund は r から v への二つの異なるバックトラックフリー歩道を持つ。よって定理 5.1.3 より Dund は閉路を持つと結論できる。しかし、これは Dund が閉路を持たない事実と矛盾する。
この矛盾は仮定が間違っていたことを示す。よって、各頂点 v∈V に対して D が r から v への路を唯一つ持つ。つまり命題 A4 は成り立つ。
[A4 ⟹ A5 の証明] 命題 A4 が成り立つと仮定する。
D の任意の弧を a とする。多重有向グラフ D∖a で r が始根でないことを示せばよい。弧 a が始点 s と終点 t を持つとする。これから D∖a が r から t への路を持たないことを背理法で示す。
D∖a が r から t への路 p を持つと仮定する。D∖a は弧 a を持たないので、p は a を含まない。
一方、成り立つと仮定している命題 A4 で v=s とすると、多重有向グラフ D には r から s への歩道が唯一つ存在すると分かる。この歩道を (v0,a1,v1,a2,v2,…,ak,vk) とする。この歩道の末尾に弧 a と頂点 t を加えると、次の歩道が得られる:
(v0,a1,v1,a2,v2,…,ak,vk,a,t)
これは r から t への歩道である。この歩道を q とする。
p と q はどちらも D における r から t への歩道である。q が弧 a を含むのに対して p は含まないので、p と q は異なる。しかし、命題 A4 を v=t として適用すると、多重有向グラフ D は r から t への路を唯一つ持つことが分かる。これは p と q という二つの異なる歩道が D に存在する事実と矛盾する。
この矛盾から仮定が偽だと分かる。つまり D∖a には r から t への路が存在しない。よって r は D∖a の始根ではない。
a を固定したことを忘れる。以上の議論から、D の任意の弧 a に対して D∖a で r が始根でないことが証明された。言い換えれば、D から任意の弧を除去すると、r が (弧を除去した後のグラフにおいて) 始根でなくなる。つまり命題 A5 は成り立つ。
最初に deg−r=0 を背理法で示す。deg−r=0 と仮定する。このとき r を終点とする弧 a が存在する。これから r が D∖a の始根だと示す。
r から始まる任意の路は終点が r の弧 a を含まない (路は同じ頂点を二度通れないため) ので、D∖a の路でもある。r は D の始根なので、D の任意の頂点 v に対して D は r から v への路を持つ。それらの路は D∖a の路でもあるので、D∖a の任意の頂点 v に対して D∖a は r から v への路を持つ。言い換えれば、r は D∖a の始根である。一方、成立を仮定した命題 A5 からは D∖a で r が始根でないと分かる。これは D∖a で r が始根である事実と矛盾する。
この矛盾から仮定が偽だと分かる。つまり deg−r=0 が証明された。
続いて v∈V∖{r} を任意に取る。deg−v=1 を示す必要がある。
背理法で示す。deg−v=1 と仮定する。r が D の始根より deg−v≥2 が分かる3。よって終点が v の異なる二つの弧 a, b が存在する。
続いて、三つの場合を分けて考える:
Case 1: 有向グラフ D∖a が r から v への路を持つ。
Case 2: 有向グラフ D∖b が r から v への路を持つ。
Case 3: 有向グラフ D∖a と有向グラフ D∖b がどちらも r から v への路を持たない。
まず Case 1 を考える。このとき有向グラフ D∖a は r から v への路 p を持つ。
成立を仮定した命題 A5 より、D から弧 a を除去した D∖a で r は始根でなくなる。始根の定義を使って言い換えれば、有向グラフ D∖a が r から w への路を持たないような頂点 w∈V が存在する。
r は有向グラフ D の始根より、D は r から w への路 q を持つ。この路 q に注目する。もし q が弧 a を含まないなら、q は D∖a の路にもなる。しかし D∖a は r から w への路を持たないので、これはあり得ない。よって路 q は弧 a を含む。
q の弧 a より後の部分を考える。この部分は v から w への路である (a の終点は v で、q の終点は w であるため)。この路を q′ とすれば、q が路なので q′ は a を含まない。よって q′ は D∖a の路である。
よって有向グラフ D∖a は r から v への路 p と v から w への路 q′ を持つ。二つの路を連結すれば、r から w への歩道 p∗q′ を得る。つまり D∖a は r から w への歩道を持つ。よって系 3.3.10 より、D∖a は r から w への路を持つと結論できる。これは D∖a が r から w への路を持たない事実と矛盾する。
よって Case 1 で矛盾が導けた。
この議論の a を b に置き換えれば、Case 2 でも同様に矛盾が導ける。
最後に Case 3 を考える。このとき有向グラフ D∖a と有向グラフ D∖b がどちらも r から v への路を持たない。一方、r は有向グラフ D の始根より D は r から v への路 p を持つ。仮に p が弧 a を含まないなら、p は D∖a における r から v への路にもなって仮定に反する。よって p は a を含む。同様の議論から p は b を含むことも分かる。しかし、二つの弧 a, b は同じ終点 v を持つので、一つの路が a と b の両方を含むことはない (路は同じ頂点を最大でも一度しか含まないため)。これは p が a と b の両方を含む事実と矛盾する。以上で Case 3 でも矛盾が導けた。
Case 1, Case 2, Case 3 のそれぞれで矛盾を導いたので、仮定が偽だと分かる。よって deg−v=1 が証明された。
任意の多重有向グラフ D に対する Dund は定義 4.4.1 で定義した。大まかに言えば、多重グラフ Dund は D の弧が持つ向きを「無視」することで得られる (平行辺はそのままとする)。例えば D= なら Dund= となる。 ↩︎
証明: r が D の始根なので、有向グラフ D は r から v への路を持つ。v∈V∖{r} より v=r だから、この路は少なくとも一つの弧を含む。この路の最後の弧は明らかに v を終点に持つ。つまり deg−v≥1 である。これと仮定の deg−v=1 を組み合わせれば deg−v≥2 を得る。 ↩︎
なら 
となる。 ↩︎