グラフ理論

任意の（穴のない）多面体について，
$V-E+F=2$

が成立する。ただし，頂点の数を $V$, 辺の数を $E$, 面の数を $F$ とした。

連結なグラフにおいて，

• 一筆書きして戻ってこれる $\iff$ 全ての頂点の次数が偶数
• （スタートとゴールが異なるような）一筆書きができる $\iff$ 次数が奇数であるものがちょうど2つ

言葉で表現すると大変なのでグラフを用います。つまり，6人をそれぞれ点で表し，知り合いを赤い線で結び，知らない人を青い線で結びます。このグラフにおいて赤い三角形か青い三角形が存在することを示せばよいです。

グラフ $G=(V,\:E)$ の頂点 $v$ の次数を $d_v$ とおくとき，

主張1：$\displaystyle\sum_{v\in V}d_v=2|E|$

マッチング $M$ について以下を満たすとき 道 $P$ は増加道であるという。

• $P$ の出発点と到着点がマッチングの端点でない
• 交互路である（$M$ に含まれていない枝と含まれている枝を交互に使う）

任意の地図は四色で塗り分けることができる。

完全グラフ $K_5$ および完全二部グラフ $K_{3,3}$ は平面的グラフでない。

点（母点）がいくつか与えられたとき，どの点に一番近いかによって平面を分割したものをボロノイ図（Voronoi diagram）と言う。

穴のない $n$ 角形の全領域を監視するために必要な監視カメラの台数は高々 $\left\lfloor\dfrac{n}{3}\right\rfloor$ 台

• 大きい三角形 $ABC$ がある。
• この三角形の周または内部にいくつかの点があり，小さい三角形たちに分割されている。
• 頂点 $A,B,C$ および各点は赤・青・緑のいずれかで塗られている。ただし以下を満たす：
  • $A,B,C$ は異なる色
  • 辺 $AB$ 上の点は $A$ または $B$ と同じ色
  • 辺 $BC$ 上の点は $B$ または $C$ と同じ色
  • 辺 $CA$ 上の点は $C$ または $A$ と同じ色

このとき，$3$ つの頂点の色が相異なるような小さい三角形が存在する。

無向グラフ $G$ に対して，$G$ の全域木の個数は，$G$ のラプラシアン行列の任意の余因子と等しい。