グラフ理論まとめ：定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】
グラフ理論の全体像を一記事で．グラフの定義から平面性・彩色・マトロイドまで，離散数学と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた．各トピックの依存関係図付き．
グラフの基礎定義と基本性質 ― グラフ理論の出発点を固める
無向グラフ・有向グラフの形式的定義から出発し，次数，握手の補題，完全グラフ$K_n$，完全二部グラフ$K_{m,n}$，グラフの同型を証明付きで解説する教科書スタイルの記事．
道と連結性 ― グラフの「つながり」を定式化する
道・径路・閉路の定義，連結成分，連結度$\kappa(G)$，切断点と橋，二部グラフ判定定理，Mengerの定理を証明する．
木と森 ― 最小限の連結構造
木の同値条件を証明し，$|E|=|V|-1$，根付き木，Cayleyの公式，全域木，最小全域木（Kruskal/Primのアルゴリズム）を扱う．
オイラーグラフとハミルトングラフ ― 道を巡る二つの古典問題
ケーニヒスベルクの橋問題からオイラーの定理，有向オイラーグラフ，ハミルトン路，OreとDiracの定理，NP完全性を解説する．
最短経路問題 ― 重み付きグラフを探索する
BFS最短路，Dijkstraの正当性証明，Bellman-Ford，負閉路検出，Warshall-Floyd，DAG上の最短路を体系的に扱う．
有向グラフとトポロジカルソート ― 順序構造としてのグラフ
強連結成分（SCC），TarjanおよびKosarajuのアルゴリズム，DAGとトポロジカルソート，半順序との対応，DAG上のDPを解説する．
マッチングと被覆 ― 最適な組み合わせを見つける
増加路，Bergeの定理，Hallの結婚定理，Königの定理，安定マッチング（Gale-Shapley），重み付きマッチングを証明付きで扱う．
ネットワークフロー ― グラフを流れるもの
フローネットワーク，最大フロー最小カット定理，Ford-Fulkerson法，Edmonds-Karp，Dinic，二部マッチングへの帰着を体系的に解説する．
平面グラフ ― 平面に描けるグラフの世界
オイラーの多面体公式$V-E+F=2$，$E \leq 3V-6$，$K_5$と$K_{3,3}$の非平面性，Kuratowskiの定理，双対グラフを証明する．
グラフ彩色 ― 何色あれば塗り分けられるか
彩色数$\chi(G)$，貪欲彩色，Brooksの定理，彩色多項式，辺彩色とVizingの定理，四色定理の概要を体系的に解説する．
代数的グラフ理論入門 ― 行列で読むグラフの構造
隣接行列，ラプラシアン$L=D-A$，行列木定理，固有値と連結性，$A^k$の$(i,j)$成分が道の数を表すことを証明する．
マトロイドと貪欲法 ― グラフの奥にある構造
マトロイドの公理，グラフ的マトロイド，貪欲法の最適性定理，MSTの再解釈，マトロイド交差を証明付きで解説する．