宿田：連結の場合に帰着してよさそう
平山：良いと思うよ
渡辺：帰納法的なことしたくなった
平山：これ順序に依存してるの面倒だな～
宿田：次数 $1$ のやつはその友達がGLにいないといけなくて
馬杉：自分自身とは友達になれないんだったね…
平山：GLにいる各人について友達が必ずGLにいるのか
渡辺：かならずペアで乗らないといけないってことか
平山：じゃあ独立ないくつかのペアに分割できれば良いってことか
宿田：グラフが五角形の時ってどんな感じになる？
平石：これ隣り合う $2$ 点を連続して取るとダメですね
宿田：$1,3,4,2$ を順にとるといいのかな
平山：まあでもペア $2$ つには分割できるよね
渡辺：ペア作って順序は考えるとか？
平山：奇数人のGLも別に存在するのがタチ悪くて
渡辺：GLを構成すること自体は簡単でしょ
平山：それは別になんでも出来て
馬杉：とりあえずある頂点 $x$ の隣接点の集合を $N(x)$ として
馬杉：頂点の集合 $S$ について $N(S)$ を各元 $x$ の $N(x)$ の合併とする
馬杉：1つ削除とか1つ追加とかができれば良いと思っていて
平山：とりあえず適当なペア $u,v$ をGLに入れるとすると、
平山：全体から $N(\{u,v\})$ を取り除いたときに孤立点が出来なければ良くて
渡辺：こっちもほぼ同じことを考えていて、同じケースで回らない
兒玉：極小なGLに $1$ 頂点追加で行けるんだろうなとは思った
馬杉：良さそうだと思います
馬杉：というか極小なGLってどう置換してもGLなんだよね
平山：上で言ったの $2$ 頂点選んでるの辛いので、適当な頂点 $v$ だけ取って
平山：全体から $v$ と $N(v)$ 除いたグラフ $G_1$ に孤立点が出来なければ
平山：まず $v$ で、そこから $G_1$ でGL作って、最後に $v$ の友人とすれば良いな
馬杉：いま $1$ つ追加できない極小GLってのがかなりキモい状況になってる
馬杉：$a_1,\cdots ,a_r$ って極小GLに頂点 $b$ を追加することを考えて
馬杉：$N(b)$ を $N(X_b)$ が覆うGLの部分集合 $X_b$ で濃度最小のものを取る
馬杉：$X_b$ の濃度が $2$ 以上の場合は適当に $b$ を挿入できるから
平山：えっ $N(b)=N(X_b)$ の場合って仕事なくなる頂点が出る可能性ない？
馬杉：置換が自由にできるのが本質で、$X_b$ が $a_1,\cdots ,a_s$ とできて
馬杉：等しいときは $(a_1,)b,a_{s+1},\cdots ,a_r$ がGLになってる
平山：あー理解した、等しくないときは簡単だな
馬杉：それで $N(b)$ が常に $N(a_{\mathrm{h}\mathrm{o}\mathrm{g}\mathrm{e}})$ と一致するとき以外はいける
平山：上のやつ少しケースが減って、単純に $v$ だけ除いたグラフ $G_2$ を考えたときに
平山：$v$ としか繋がってない頂点が無ければ、$G_2$ のGLが全体でもOKになる
平山：というのも $G_1$ に孤立点があることから $v$ の友人がGLに入っている
馬杉：出来た気がする、$N(b)$ が常に $N(a_{\mathrm{h}\mathrm{o}\mathrm{g}\mathrm{e}})$ と一致するときグラフが $r$-彩色可能で
馬杉：そのとき色 $i$ と $j$ がどこかで隣接してれば全部の組で隣接してるから
馬杉：各色を一つにまとめて、要するに極小GLが全体であるとみなせる
馬杉：でもそうなるケースってdisjointな辺の集まりだから、終わります
平山：僕も終わったと思う、$G_1$ に孤立点があり、$v$ としか繋がってない頂点 $u$ があるとして
平山：$G_1$ の孤立点以外でGLを作り、さらに孤立点を覆うように $N(v)$ からいくつか選ぶ
平山：そのとき $(u,)v$ とまず選んで、次にGLを持ってきて、最後に孤立点を覆う頂点たちを使う
平石：いけてると思う
宿田：ようやく、追いきった。
渡辺：やっとわかった
平山：馬杉のもいけてると思う、すごいな
宿田：というかこれ2番級の配置なのか…

• 工事中

生徒を頂点とし, 友人関係にある $2$ 人の間に無向辺を張ったグラフ $G$ 上で考える. $G$ において, 頂点 $v$ の隣接点全体の集合を $N(v)$ とし, 頂点の集合 $S$ に対し各元 $v$ の $N(v)$ の合併を $N(S)$ で表す.

解法1.　$G$ の頂点数についての数学的帰納法によって示す. $2$ 頂点の場合は明らかである. 以下 $G$ が $m(\ge 3)$ 頂点からなるとして, 頂点数 $m$ 未満で常に成立すると仮定して成立を示せばよい.

ある頂点 $v$ を適当に固定し, $G$ から $v$ と $N(v)$ およびこれらに接続する辺を削除したグラフ $G_1$ を考える. この $G_1$ に孤立点が存在しないとき, $G_1$ で条件をみたすGLをとり, その前に $v$ を, 後ろに適当な $v$ の隣接点を加えたものは, $G$ において条件をみたすGLである. したがって, 以下 $G_1$ に孤立点が存在するとする.

$G$ から $v$ および $v$ に接続する辺を削除したグラフ $G_2$ を考える. このとき $G_2$ において条件をみたすGLを考えると, $G_1$ に孤立点が存在するという仮定から, このGLには必ず $v$ の隣接点が含まれる. したがって, これは $G$ 全体でも条件をみたすGLであるから, 以下 $G_2$ にも孤立点 $u$ が存在するとする.

このとき, まず $G_1$ で条件をみたすGLをとり, その前に $v$ を, 後ろに $G_1$ の孤立点と隣接する頂点すべてを加えたものは, $G$ においてもGLである. さらに前に $u$ を加えたものもGLであるから, 以上よりすべての場合で成立が示された.

解法2.　工事中