太郎さんと花子さんが教室Zoomで会話している—
太郎：ねえ花子さん、木は2部なのかな？
花子：木って何？
太郎：ああ、花子さんはまだグラフ理論を履修していなかったんだ。じゃあ簡単に定義から述べてみるね。
花子：うん、お願い。
定義（グラフ）
グラフとは、次のような集合 V, E の組である。
i) V の要素は頂点とよばれる。
ii) E の要素は相異なる2頂点の非順序対であり、辺とよばれる。
定義（頂点の次数）
頂点 v を端点にもつ辺の個数を v の次数という。
太郎：グラフ G の頂点集合・辺集合を強調したいときは G(V, E) と表記するよ。V, E が有限であるようなグラフを有限グラフというんだ。今回は有限グラフのみを考えることにするね。
花子：わかった。
太郎：それから、E の性質から明らかにループ（頂点自身への辺）や多重辺（同じ2頂点間を結ぶ複数の辺）は許されないんだ。ちなみに、ループや多重辺を許すものを多重グラフ、許さないものを単純グラフとよぶこともあるようだね。
花子：なるほどね。続けて。
定義（歩道）
歩道とは、頂点と辺の交互列
v0, e1, v1, ..., en, vn
である。n を歩道の長さとよぶ。v0 を（歩道の）始まり、vn を（歩道の）終わりとよぶ。とくに始まりと終わりが同じであるとき、歩道が閉じているという。
定義（道）
道とは、すべての頂点が異なる歩道である。
定義（閉路）
閉路とは、終わりを除くすべての頂点が始まりと相異なる閉じた歩道である。
花子：ちょっと待って。歩道とか道とか、ちょっと分かりにくいネーミングじゃない？
太郎：確かに。英語表記だと歩道は walk、道は path、閉路は cycle っていうらしいよ。
花子：英語もあわせて覚えると混乱しなくて済みそうだね。
定義（連結）
グラフの任意の2頂点間に道が存在するとき、グラフは連結であるという。
定義（木）
木とは、閉路を持たない連結なグラフである。
太郎：頂点が1個の木は退化木とよばれるけど、今回は退化木は考えない。つまり、頂点が2個以上の木だけを考えることにするよ。
花子：わかった。
太郎：余談だけど、閉路を持たないグラフで連結とは限らないものを森というんだ。林とよぶ本もあるらしいよ。だから木は森であり林なんだね。
花子：大自然を感じるね。
定義（2部）
グラフ G(V, E) について、V がある部分集合 V1, V2 に分割され、E の任意の辺が V1 の頂点と V2 の頂点を結んでいるとき、G は2部であるという。
太郎：必要な定義はこのくらいかな。
花子：ありがとう。ええと、木は次数1の頂点を持つんだよね。
太郎：というと？
花子：木の頂点をひとつ固定して根とよぶことにするよ。頂点 v を任意にとる。木は閉路を持たず連結であるから、根を始まりとし v を終わりとする道がただひとつ存在する。このような道の長さを d とおく。v の次数が1ならば主張が成立する。v の次数が2以上ならば、根を始まりとし v を含む道であって長さが d より大きいものが存在するから、このような道の終わりを v とおきなおして同じ議論を繰り返せば、グラフが有限であることから最終的に次数1の頂点に到達する。違う？
太郎：ああ、そうかも。
花子：じゃああとは簡単だよ。自然数 n の条件 P(n) を「頂点数 n の木は2部である」と定義する。頂点が2個の木は2部であるから、P(2) が成立する。つぎに任意の n, n≧2 に対して P(n) の成立を仮定して、頂点数 n の任意の木をとる。この木の次数1の頂点に新たな辺と頂点をつなげたグラフは木かつ2部であるから P(n+1) が成立する。したがって、任意の n, n≧2 に対して P(n) が成立する。すなわち木は2部である。簡単だね。
太郎：花子さん、本当に未履修なの？
数学の入試問題は問題文が短いと話題になったりしますが、問題文の短さでいうと「木は2部か？」は個人的に結構好きな問題です。ところで葉（木がもつ次数1の頂点）に関する帰納法は Leaf Reduction ともよばれると聞いた覚えがありますが、ソースが見つからずなんとも言えません。全体を通して誤りがあれば（たぶんありそうですが）修正しますのでご指摘くださると幸いです。
参考文献
- マグロウヒル大学演習 離散数学 コンピュータサイエンスの基礎数学
