MathLabs

第6問

平面上の有限個の点が与えられ、各点は整数座標をもつ。座標軸のいずれかに平行な任意の直線 LL 上で、その直線 LL 上の白点数と赤点数の差の絶対値が高々 11 となるように、常に点を赤または白に塗り分けられるか。
ステップ 1/4: 二部グラフを作る
ざっくり言うと

点は自然に一辺とみなせる。その行と列が二つの端点である。軸に平行な直線上の彩色の均衡は、グラフの頂点に接する辺の彩色の均衡になる。

V=H⊔W,p=(h,w)↔hwV=H\sqcup W,\qquad p=(h,w)\leftrightarrow hw
行と列の二部分割を示す K3,3 の図。頂点色は二つの部を表す。
三つの行側頂点と三つの列側頂点をもつ完全二部グラフ。
詳しい解説

点を含む水平線ごとに一つの頂点、垂直線ごとに別の頂点を置く。点 (h,w)(h,w) を行頂点 hh と列頂点 ww を結ぶ辺とする。これは二部グラフであり、辺の赤白彩色が点の彩色に対応し、各直線の条件は頂点条件そのものである。