ナッシュ・ウィリアムズの定理

グラフ理論 において、ナッシュ＝ウィリアムズの定理は、グラフが辺が互いに素な全域木（より一般的には森）をいくつ持つことができるかを記述する木詰め定理です。

グラフGにはt本の辺互いに素な全域木が存在する場合と、少なくともt ( k  −1)本の交差辺が存在する場合の両者が等しい場合とがある( Tutte 1961、Nash-Williams 1961)。^{[1] [2]}${\textstyle V_{1},\ldots ,V_{k}\subset V(G)}$${\displaystyle V_{i}\neq \emptyset }$

この記事では、このようなグラフはt樹木性 を持つ、またはt -樹木性であると言います。(実際の樹木性の定義は少し異なり、木ではなく森林に適用されます。)

k樹木グラフは必ずk辺で連結されます。逆は真ではありません 。

NW の帰結として、すべての 2 k辺連結グラフはk樹状グラフです。

NW 定理とメンガーの定理はどちらも、グラフが2 つの頂点間にk個の辺が互いに素なパスを持つ場合を特徴付けます。

1964年、ナッシュ・ウィリアムズ^[3]は上記の結果を森林に一般化した。

G は、任意の に対して、誘導サブグラフG [ U ] が最大で 個のエッジを持つ場合、そのときに限り、 t個のエッジ分離フォレストに分割できます。${\displaystyle U\subset V(G)}$ ${\displaystyle t(|U|-1)}$

証明はここに示されています。^{[4] [2]}

これは通常、グラフがt -aboricであるという意味を定義する方法です。

言い換えれば、すべてのサブグラフS =  G [ U ] に対して、 が成り立ちます。不等式を飽和させるサブグラフSが存在するという点でタイトです(そうでなければ、より小さな t を選択できます)。これにより、次の式が導かれます。${\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil }$

${\displaystyle t=\lceil \max _{S\subset G}{\frac {E(S)}{V(S)-1}}\rceil }$

NW 式とも呼ばれます。

一般的な問題は、グラフがエッジが互いに素なサブグラフによってカバーされる可能性があるかどうかを尋ねることです。

• 樹木性
• ブリッジ（カットエッジ）
• マトロイド分割
• メンガーの定理
• 木パッキング予想

• ポールソン、ローレンス C.ナッシュ-ウィリアムズ分割定理 (Isabelle/HOL における形式的証明の開発、形式的証明のアーカイブ)