グラフ理論 50 本ノック

学部50 問。全問無料です。

対象読者: 本テーマの記事（次数列・Euler 回路、マッチング、連結度とフロー、平面グラフ、Kuratowski の定理、彩色、Turán と Ramsey）を読んだ学部生。小さなグラフでの計算と定理の仮定の確認ができる人。

テーマの目次へ（グラフ理論）

執筆: Claude Code（Sonnet 5.5）・監査 2 回（Claude Code）・最終 2026-10-12

読み込んでいます…

この冊について（出典・構成・使う定理）

主な参考文献

• R. Diestel, Graph Theory
• D. B. West, Introduction to Graph Theory
• J. A. Bondy, U. S. R. Murty, Graph Theory
• B. Bollobás, Modern Graph Theory

問題はすべて Rikai の書き下ろしです。参考文献の演習や本文は転載していません。

構成

• 1〜8: 次数列・Euler 回路・Hamilton 閉路
• 9〜16: マッチングと被覆
• 17〜24: 連結度とネットワークフロー
• 25〜31: 平面グラフと Euler の公式
• 32〜36: Kuratowski の定理とマイナー
• 37〜43: 彩色
• 44〜50: 極値問題と Ramsey 理論

形式: 単一選択 17・複数選択 7・○× 7・数値 8・並べ替え 3・誤り探し 4・記述 4。難易度 ★〜★★★★: 8 / 28 / 14 / 0。

この冊で使う定義・定理（79）

• 定義 3.3 ブロック・ブロック木 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 24 番
• 定義 2.1 頂点連結度・辺連結度 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 19, 20 番
• 定義 4.2 カット 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 18, 22 番
• 定義 5.1 内素な道・辺素な道 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 21 番
• 定義 4.1 有向グラフ・ネットワーク・フロー 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 17 番
• 補題 4.3 流量はどのカットでも測れる 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 17 番
• 補題 4.6 増加道が無ければ流量と等しい容量のカットがある 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 23 番
• 命題 3.4 ブロック木は木である 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 24 番
• 注意 4.12 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 23 番
• 定理 4.9 整数性定理 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 22, 23 番
• 定理 4.8 最大フロー最小カット定理 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 17, 18, 22 番
• 定理 5.4 Menger の定理 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 21 番
• 定理 2.2 Whitney の不等式 連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理 → 19, 20 番
• 定義 3.1 極値数・Turán グラフ 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 44 番
• 定義 2.1 有限確率空間 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 49 番
• 定義 5.1 Ramsey 数 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 47, 49, 50 番
• 命題 4.3 長さ 4 の閉路を含まないグラフ 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 48 番
• 命題 5.6 小さい Ramsey 数 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 47 番
• 定理 4.2 Kővári–Sós–Turán の定理 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 48 番
• 定理 3.3 Mantel の定理 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 45, 46, 48 番
• 定理 5.2 Ramsey の定理 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 47, 49, 50 番
• 定理 3.4 Turán の定理 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 → 44, 45, 48 番
• 系 6.3 木と閉路の彩色多項式 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 39 番
• 定義 2.1 彩色・彩色数・クリーク数 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 37, 41, 43 番
• 定義 6.1 彩色の個数 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 39 番
• 定義 2.2 縮退数・彩色数（coloring number） 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 42 番
• 定義 5.1 辺彩色・辺彩色数 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 40 番
• 命題 2.3 彩色数の基本的な評価 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 37, 38, 41, 42, 43 番
• 定理 4.3 Brooks の定理 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 38 番
• 定理 6.2 彩色多項式 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 39 番
• 定理 5.3 König の辺彩色定理 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 40 番
• 定理 5.5 Vizing の定理 彩色：Brooks の定理・Vizing の定理・彩色多項式 → 40 番
• 系 7.5 外平面的グラフの特徴づけ Kuratowski の定理：マイナーと平面性の判定 → 36 番
• 定義 3.2 縮約・マイナー・禁止マイナー Kuratowski の定理：マイナーと平面性の判定 → 35, 36 番
• 定義 3.1 細分・位相的マイナー Kuratowski の定理：マイナーと平面性の判定 → 32, 33, 34 番
• 補題 3.6 マイナーと位相的マイナー Kuratowski の定理：マイナーと平面性の判定 → 35 番
• 命題 3.4 平面性は部分グラフ・細分・縮約で保たれる Kuratowski の定理：マイナーと平面性の判定 → 33, 35 番
• 定理 6.5 Kuratowski の定理 Kuratowski の定理：マイナーと平面性の判定 → 32, 33, 34 番
• 定理 7.1 Whitney の一意性定理 Kuratowski の定理：マイナーと平面性の判定 → 35 番
• 系 4.3 不足数版 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 10 番
• 系 4.5 正則二部グラフの完全マッチング マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 11, 16 番
• 定義 3.1 交互道・増加道 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 14 番
• 定義 2.1 マッチング マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 9, 13, 15 番
• 定義 7.1 奇成分 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 12 番
• 補題 2.3 弱双対性 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 9 番
• 定理 3.3 Berge の定理 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 14 番
• 定理 5.1 Gallai の恒等式 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 13 番
• 定理 4.2 Hall の結婚定理 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 10, 11, 15, 16 番
• 定理 4.9 König–Egerváry の定理 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 9, 13 番
• 定理 7.2 Tutte の 1-因子定理 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 11 番
• 定理 7.5 Tutte–Berge の公式 マッチング：Hall の結婚定理・König の定理・Tutte の定理 → 12 番
• 系 5.4 閉じていない Euler 小道 道・閉路・木：Euler 回路と Hamilton 閉路 → 4 番
• 定義 6.8 閉包 道・閉路・木：Euler 回路と Hamilton 閉路 → 8 番
• 定義 2.1 隣接・次数 道・閉路・木：Euler 回路と Hamilton 閉路 → 2 番
• 定義 7.1 次数列・グラフ的な列 道・閉路・木：Euler 回路と Hamilton 閉路 → 1 番
• 定義 5.1 Euler 回路・Euler 小道 道・閉路・木：Euler 回路と Hamilton 閉路 → 3 番
• 定義 2.4 部分グラフ・補グラフ・特別なグラフ 道・閉路・木：Euler 回路と Hamilton 閉路 → 31, 37 番
• 定義 2.3 歩道・小道・道・閉路 道・閉路・木：Euler 回路と Hamilton 閉路 → 5 番
• 補題 2.2 握手補題 道・閉路・木：Euler 回路と Hamilton 閉路 → 2, 4, 46 番
• 補題 5.2 小道が頂点で使う辺の数 道・閉路・木：Euler 回路と Hamilton 閉路 → 7 番
• 命題 6.2 Hamilton 閉路の必要条件 道・閉路・木：Euler 回路と Hamilton 閉路 → 6 番
• 命題 3.1 最小次数と長い道・長い閉路 道・閉路・木：Euler 回路と Hamilton 閉路 → 5 番
• 定理 6.9 Bondy–Chvátal の閉包定理 道・閉路・木：Euler 回路と Hamilton 閉路 → 8 番
• 定理 6.6 Dirac の定理 道・閉路・木：Euler 回路と Hamilton 閉路 → 6, 8 番
• 定理 5.3 Euler の定理 道・閉路・木：Euler 回路と Hamilton 閉路 → 3, 4, 7 番
• 定理 7.2 Havel–Hakimi の定理 道・閉路・木：Euler 回路と Hamilton 閉路 → 1 番
• 定理 6.5 Ore の定理 道・閉路・木：Euler 回路と Hamilton 閉路 → 6, 8 番
• 系 3.5 次数 5 以下の頂点 平面グラフ：Euler の公式・双対・五色定理 → 28 番
• 系 3.4 K_5 と K_{3,3} は平面的でない 平面グラフ：Euler の公式・双対・五色定理 → 28 番
• 系 3.3 平面的グラフの辺数の上界 平面グラフ：Euler の公式・双対・五色定理 → 26, 28, 31, 32 番
• 定義 4.3 双対グラフ 平面グラフ：Euler の公式・双対・五色定理 → 29 番
• 定義 2.6 面の境界・面の次数 平面グラフ：Euler の公式・双対・五色定理 → 27 番
• 定義 6.4 外平面的グラフ 平面グラフ：Euler の公式・双対・五色定理 → 36 番
• 定義 2.2 平面グラフ・平面的グラフ・面 平面グラフ：Euler の公式・双対・五色定理 → 25 番
• 命題 4.5 双対グラフの基本性質 平面グラフ：Euler の公式・双対・五色定理 → 29 番
• 定理 3.1 Euler の公式 平面グラフ：Euler の公式・双対・五色定理 → 25, 26, 27, 29, 30 番
• 定理 6.3 五色定理 平面グラフ：Euler の公式・双対・五色定理 → 41 番
• 定理 6.8 四色定理 平面グラフ：Euler の公式・双対・五色定理 → 28 番
• 定理 5.1 正多面体は 5 種類 平面グラフ：Euler の公式・双対・五色定理 → 30 番