有名かもしれない事実
最大流-最小カット定理
フローネットワークで $s-t$ 最大流と最小カットは等しい．
DAGの最小パス被覆
DAGの頂点 $v$ を $v, v'$ に分裂させ辺 $(u,v)$ が存在するなら $u_i \to v_i'$ に流量 $1$ の辺を張る．$n - ( \{ v \_i \}, \{ v \_i' \}$ の二部マッチング) 本のパスで DAG を被覆できる．
行列木定理
無向グラフ $G$ のラプラシアン行列 $A$ を， $a_{ij} = $ 頂点 $i$ の次数 ($i=j$), $v_i-v_j$ 間の辺の数 $(i \neq j)$ で定義する． $A$ の $n$ 行 $n$ 列を削ってできる $(n-1)\times(n-1)$ 行列の $\det$ は $G$ の全域木の個数に等しい．
特に木のとき $n^{n-2}$ 個.
参考 グラフと線形代数
全域木への分解の可能性判定
無向グラフに Disjointな $k$ 個の全域木が存在する $\iff$ 任意の頂点の $r$ 分割に対して，異なる集合間を結ぶ辺が $k(r-1)$ 個以上存在する