一筆書きとグラフ

正方形 $P_1P_2P_3P_4$ に 2 本の対角線をかき、その交点を $O$ とする。さらに上の辺 $P_4P_3$ の上に三角形の屋根 $P_4RP_3$ をのせる（図1 の左）。線は、正方形の 4 辺、対角線を $O$ で区切った 4 本（$P_1O$、$OP_3$、$P_2O$、$OP_4$）、屋根の 2 本（$P_4R$、$RP_3$）の、合わせて $10$ 本である。
$P_1$ から始めて、次の順にたどる。
$$ P_1\to P_2\to O\to P_1\to P_4\to O\to P_3\to P_4\to R\to P_3\to P_2 $$
通った線を順に書くと、$P_1P_2$、$P_2O$、$OP_1$、$P_1P_4$、$P_4O$、$OP_3$、$P_3P_4$、$P_4R$、$RP_3$、$P_3P_2$ の $10$ 本で、どれも 1 回ずつ現れ、$10$ 本すべてを通っている。よって家の形は一筆書きできる。始点は $P_1$、終点は $P_2$ で、出発点には戻っていない。

家の形から屋根の 2 本を取り除いた図（正方形と 2 本の対角線。図1 の右）を考える。線は $8$ 本である。いろいろな点から始めて試しても、どうしても線が残ってしまう。たとえば $P_1\to P_2\to O\to P_1\to P_4\to O\to P_3$ とたどると、$P_2P_3$ と $P_3P_4$ の 2 本が残る。$P_3$ から $P_4$ へ進んでも $P_2P_3$ が残り、$P_2$ へ進んでも $P_3P_4$ が残る。
試した順番がまずかっただけなのか、どうやっても無理なのかは、試すだけでは分からない。どうやっても無理であることは、後の ex-epg-envelope-proof で証明する。

18 世紀のプロイセンの町 Königsberg（ケーニヒスベルク）には川が流れ、中の島 $A$、北岸 $B$、南岸 $C$、東の陸地 $D$ の 4 つの陸地が、7 本の橋で結ばれていた（図2 の左）。橋のつながり方は次のとおりである。

「7 本の橋をちょうど 1 回ずつ渡って町を歩くことはできるか」という問いが知られていた。陸地を点、橋を線でかくと（図2 の右）、これはその図の一筆書きの問題になる。Euler はこの問いを考え、できないことを示した（Eul41）。KT17 §5.3（p. 75）は Euler がこの問題を 1736 年に解決したとする。論文はペテルブルク科学アカデミー紀要の 1736 年の巻に載ったが、その巻の刊行は 1741 年である。本記事では ex-epg-konigsberg-answer で答える。

1. Königsberg の橋のグラフ（ex-epg-konigsberg、図2 の右）。$A$ には $A$–$B$ の 2 本、$A$–$C$ の 2 本、$A$–$D$ の 1 本がつながるので $\deg A=2+2+1=5$ である。同じように $\deg B=2+1=3$（$A$–$B$ の 2 本と $B$–$D$）、$\deg C=2+1=3$、$\deg D=1+1+1=3$（$A$–$D$、$B$–$D$、$C$–$D$）である。4 つとも奇数次である。
2. 家の形（ex-epg-house）。$P_1$ には $P_1P_2$、$P_1P_4$、$P_1O$ の 3 本がつながるので $\deg P_1=3$ である。同じように $\deg P_2=3$、$\deg P_3=4$（$P_3P_2$、$P_3P_4$、$OP_3$、$RP_3$）、$\deg P_4=4$、$\deg O=4$、$\deg R=2$ である。奇数次の頂点は $P_1$、$P_2$ の 2 個である。
3. 封筒の形（ex-epg-envelope）では、屋根がないので $\deg P_3=\deg P_4=3$ になる。$\deg P_1=\deg P_2=3$、$\deg O=4$ で、奇数次の頂点は $P_1,P_2,P_3,P_4$ の 4 個である。

家の形（ex-epg-house）で考える。

1. $P_1\to O\to P_3\to P_4\to O\to P_1$ は長さ $5$ の閉じた道筋で、辺 $P_1O$、$OP_3$、$P_3P_4$、$P_4O$、$OP_1$ は、1 本目と 5 本目が同じ辺 $P_1O$ である。よって辺を重複しない道筋ではない。頂点 $O$ が 2 回現れるのは構わないが、辺が 2 回現れるのは許されない。
2. $P_1\to P_2\to P_3\to P_4\to P_1$ は長さ $4$ の閉じた道筋で、4 本の辺はすべて異なるので、辺を重複しない閉じた道筋である。すべての辺を通ってはいないので、一筆書きではない。
3. $P_1\to P_3$ は道筋ではない。$P_1$ と $P_3$ を直接結ぶ辺はない（対角線は $O$ で区切られている）からである。

1. Königsberg（ex-epg-degree の 1）：$5+3+3+3=14=2\times7$。
2. 家の形（ex-epg-degree の 2）：$3+3+4+4+4+2=20=2\times10$。
3. 正八面体の頂点と辺でできたグラフ（図3）：頂点は $6$ 個で、どの頂点も、向かい合う 1 つを除く $4$ 個の頂点と辺で結ばれるので次数は $4$ である。次数の和は $6\times4=24$ で、thm-epg-degree-sum から辺は $24\mathbin{÷}2=12$ 本である。正八面体の辺の数 $12$ と一致する。

1. 5 人が集まり、全員がちょうど 3 人と握手した、ということは起こらない。人を頂点、握手を辺とするグラフでは、5 個の頂点がすべて次数 $3$（奇数）になり、奇数次の頂点が $5$ 個（奇数個）になって cor-epg-odd-vertices に反するからである。次数の和で見ても、$5\times3=15$ は奇数で、辺の数の 2 倍になりえない。
2. 6 人なら、全員がちょうど 3 人と握手することは起こりうる。6 人を $1,2,3,4,5,6$ とし、$1$–$2$、$2$–$3$、$3$–$4$、$4$–$5$、$5$–$6$、$6$–$1$（輪の隣どうし）と、$1$–$4$、$2$–$5$、$3$–$6$（向かい合う人どうし）の 9 回握手すればよい。次数の和は $6\times3=18=2\times9$ である。

ex-epg-house の一筆書き $P_1\to P_2\to O\to P_1\to P_4\to O\to P_3\to P_4\to R\to P_3\to P_2$ は、すべての辺を通るので、$t(v)=\deg v$ である。

• 始点 $P_1$ は、始点の場所と途中の場所（4 番目）に 1 回ずつ現れ、$t(P_1)=1+2=3$。
• 終点 $P_2$ は、途中の場所（2 番目）と終点の場所に現れ、$t(P_2)=2+1=3$。
• $O$ は途中の場所に 2 回現れ、$t(O)=2+2=4$。$P_3$、$P_4$ も途中に 2 回ずつで $4$、$R$ は途中に 1 回で $2$。
  どれも ex-epg-degree の 2 の次数と一致し、奇数になるのは始点と終点だけである。

正八面体の頂点を、上の頂点 $N$、下の頂点 $S$、まわりの 4 つの頂点 $a,b,c,d$（この順に輪になって隣り合う）とする（図3）。辺は $N$ と $a,b,c,d$ の 4 本、$S$ と $a,b,c,d$ の 4 本、輪の $ab$、$bc$、$cd$、$da$ の 4 本で、合わせて $12$ 本である。どの頂点も次数 $4$ で偶数である。
段 1（行けるところまで進む）。$N$ から $N\to a\to b\to N\to c\to d\to N$ と進むと、$N$ の 4 本の辺をすべて使ってしまい、$N$ で進めなくなる。lem-epg-stuck のとおり、行き詰まったのは出発点 $N$ である。この閉じた道筋を $C$ とする（図3 の青）。
段 2（残りのグラフ）。$C$ が使わなかった辺は $Sa$、$Sb$、$Sc$、$Sd$、$bc$、$da$ の 6 本である。残りのグラフでの次数は $S$ が $4$、$a,b,c,d$ が $2$ で、すべて偶数である（prf-thm-epg-euler の段 4）。
段 3（$C$ の上の頂点から、残りで閉じた道筋を作る）。$C$ の上の頂点 $a$ には残りの辺 $Sa$、$da$ がある。$a$ から $a\to S\to b\to c\to S\to d\to a$ と進むと、残りの 6 本をすべて使って $a$ に戻る。これを $D$ とする（図3 の赤）。
段 4（つなぐ）。$C$ の中の最初の $a$ に着いたところで $D$ を差し込むと
$$ N\to a\to S\to b\to c\to S\to d\to a\to b\to N\to c\to d\to N $$
となる。12 本の辺をちょうど 1 回ずつ通る閉じた一筆書きである（図3 の数字の順）。

1. Königsberg のグラフは連結で、ex-epg-degree の 1 から奇数次の頂点が $A,B,C,D$ の 4 個ある。thm-epg-euler により、奇数次の頂点が $0$ 個でも $2$ 個でもないので、一筆書きはできない。つまり、7 本の橋をちょうど 1 回ずつ渡って歩くことはできない。出発点に戻らなくてよいとしても、できない。
2. 北岸 $B$ と南岸 $C$ を結ぶ 8 本目の橋をかけたとする。次数は $\deg B=4$、$\deg C=4$ に増え、$\deg A=5$、$\deg D=3$ はそのままなので、奇数次の頂点は $A$ と $D$ の 2 個になる。thm-epg-euler の 2 により、$A$ から $D$ への一筆書きがある。実際、$A\to B\to A\to C\to A\to D\to B\to C\to D$ とたどればよい。ここで 1 回目の $A\to B$ と 2 回目の $B\to A$ は $A$–$B$ の 2 本の橋を 1 本ずつ使い、$A\to C$ と $C\to A$ も $A$–$C$ の 2 本の橋を 1 本ずつ使う。$D\to B$、$B\to C$、$C\to D$ はそれぞれ $B$–$D$、新しい橋、$C$–$D$ である。8 本の橋を 1 回ずつ渡っている。

封筒の形（ex-epg-envelope）は連結で、ex-epg-degree の 3 から奇数次の頂点が $P_1,P_2,P_3,P_4$ の 4 個ある。thm-epg-euler により一筆書きはできない。これで ex-epg-envelope で試しても線が残ったことが、順番のせいではないと分かった。
cor-epg-strokes で $k=2$ なので、2 筆でかける。たとえば
$$ P_1\to P_2\to O\to P_1\to P_4\to O\to P_3,\qquad P_2\to P_3\to P_4 $$
の 2 本で、1 本目は $P_1P_2$、$P_2O$、$OP_1$、$P_1P_4$、$P_4O$、$OP_3$ の 6 本、2 本目は $P_2P_3$、$P_3P_4$ の 2 本を通り、合わせて 8 本の辺をちょうど 1 回ずつ通る。1 本目は奇数次の頂点 $P_1$ から $P_3$ へ、2 本目は $P_2$ から $P_4$ へ進んでいる。
Königsberg の 7 本の橋も、奇数次の頂点が 4 個なので、ちょうど 2 回に分ければ渡りきれる。

頂点 $1,2,3$ を結ぶ三角形と、頂点 $4,5,6$ を結ぶ三角形の、離れた 2 つからなるグラフを考える。辺は $12$、$23$、$31$、$45$、$56$、$64$ の 6 本で、どの頂点も次数 $2$（偶数）である。
しかし一筆書きはできない。道筋では、隣り合う 2 頂点は辺で結ばれている。$\{1,2,3\}$ の頂点と $\{4,5,6\}$ の頂点を結ぶ辺はないので、$\{1,2,3\}$ の頂点から出発した道筋は、ずっと $\{1,2,3\}$ の中にとどまり、辺 $45$ を通れない。$\{4,5,6\}$ から出発しても同じで、辺 $12$ を通れない。
満たす性質：すべての頂点が偶数次。満たさない性質：連結であること。破る主張：thm-epg-euler の 1 の「すべて偶数次なら閉じた一筆書きができる」。

家の形（ex-epg-house）では、奇数次の頂点は $P_1$、$P_2$ の 2 個なので一筆書きができる。しかし、偶数次の頂点 $O$ から始める一筆書きはない。
理由：$O$ から始まる一筆書きがあったとする。すべての辺を通るので $t(v)=\deg v$ である。終点が $O$ でなければ、lem-epg-count の 1 により $t(O)$ は奇数だが、$\deg O=4$ は偶数で矛盾する。終点が $O$ なら閉じた一筆書きになり、lem-epg-count の 2 により $t(P_1)=\deg P_1=3$ が偶数でなければならず、矛盾する。
thm-epg-euler の 2 が「始点と終点はその 2 個の頂点」と言っているのは、この意味である。実際に一筆書きをかくときは、まず次数を数えて、奇数次の頂点から始めればよい。

すべての頂点をちょうど 1 回ずつ通って出発点に戻る閉じた道筋を Hamilton閉路 という。一筆書き（すべての辺をちょうど 1 回ずつ）と似ているが、次数では判定できない。

1. Königsberg のグラフ（ex-epg-konigsberg）は、奇数次の頂点が 4 個で一筆書きできない。しかし $B\to A\to C\to D\to B$ は、辺 $A$–$B$（2 本のうちの 1 本）、$A$–$C$（2 本のうちの 1 本）、$C$–$D$、$D$–$B$ を通り、4 つの陸地を 1 回ずつ訪れて $B$ に戻る。
2. 頂点 $x$ を共有する 2 つの三角形 $x,p,q$ と $x,r,s$ からなる「蝶ネクタイ」の形のグラフでは、$\deg x=4$、ほかの頂点は次数 $2$ で、すべて偶数次かつ連結なので、閉じた一筆書き $x\to p\to q\to x\to r\to s\to x$ がある。しかし、すべての頂点を 1 回ずつ通って戻る閉じた道筋はない。$p$ から $r$ に行くには必ず $x$ を通り（$p,q$ と $r,s$ を直接結ぶ辺はない）、$r$ の側から $p$ の側に戻るにもまた $x$ を通るので、$x$ を 2 回通ることになるからである。
   満たす性質・満たさない性質：1 は次数の条件を満たさないのに頂点を 1 回ずつ通れ、2 は次数の条件を満たすのに頂点を 1 回ずつは通れない。破る主張：「頂点を 1 回ずつ通れるかどうかも次数で決まる」という類推。頂点を 1 回ずつ通る道筋については、次数のような簡単な判定法は知られていない（後の「大学数学で見ると」の節）。

問題の内容（本記事による要約）：$m\times n$ のマス目の各マスを黒か白に塗る。どの黒マスについても、それと 1 辺を共有する黒マスの個数が奇数であるように塗られているとする。このとき、黒マスの総数は偶数であることを示せ。
— 2001 年日本数学オリンピック本選（2001 年 2 月 11 日）問題 1（Oly01）
小さな場合で確かめる。

1. $1\times2$ のマス目の 2 マスとも黒：どちらの黒マスも、隣の黒マスは 1 個（奇数）で条件を満たす。黒マスは $2$ 個。
2. $1\times5$ のマス目を「黒黒白黒黒」と塗る：どの黒マスも隣の黒マスは 1 個で条件を満たす。黒マスは $4$ 個。
3. $1\times3$ のマス目の 3 マスとも黒：真ん中の黒マスは隣の黒マスが 2 個（偶数）なので条件を満たさない。黒マスが奇数個（3 個）になるこの塗り方は、条件の外にある。