ひと筆書きの散歩道
九州大学公開講座「現代数学入門」∗

2023 年 8 月 9 日

はじめに
数学という学問は新しい理論や定理の発見を主たる目的としています．数学において新しい理論が作られる
時，それはおよそ次のような流れを取ります：

1. 科学や実社会に現れる現象から新しい問題を提起する
2. 考える現象を記述する為の数学的な言葉・枠組みを導入する
3. 導入した枠組みの中で，多くの実験（計算）・検証を行い，予想を立てる
4. 考案した予想に対し，論理的な証明を与える
5. 同種の問題などに広く適用できるように得られた定理を改良する
この講座では，「どのような図形が一筆書きできるだろうか？」という身近な問題を題材として，上に挙げた１〜５の行程が実際にどのように進んでゆくのかを紹介します．この問題自体はよく知られていて，既に答えをご存知の方もいらっしゃるでしょう．そういう方にもこの講座を楽しんでいただけるように，随所で寄り道を交えながら，素朴な直感が厳密な数学の言葉で綴られるまでを散策してみたいと思います．

1 問題はどこから来るのか？
数学の問題というのはどこから発生するのでしょうか？物理学において万有引力の法則が「物体は何故落下するのか？」という素朴な疑問から発見されたように，数学の理論にも素朴な疑問から発生したものが沢山あります．現代数学における重要な分野の一つに，グラフ理論と呼ばれる分野がありますが，このグラフ理論
は，ケーニヒスベルグの橋の問題と呼ばれる素朴な問題が発祥であるといわれています．

ケーニヒスベルグの橋の問題
１８世紀初頭，プロイセン王国の首都ケーニヒスベルグ*1 でのことです．ケーニヒスベルグの街には，プレーゲル川という大きな川が流れており，その川には下記の図のように，七つの橋が架けられていました．あるとき街の人が次の問題を提起しました．「プレーゲル川に架かっている七つの橋を全部渡って，元の場所に帰ってくることができるか．ただし，どこから出発してもよいが，同じ橋を２度渡ってはいけない．
」∗ このテキストは，2011 年度に開催された教員免許更新講座「論理と証明 ̶数学におけるものの考え方̶」をベースにしています．

オリジナルの著者は，村井聡氏 (現・早稲田大学・教授) と鍛冶静雄 (九州大学マス・フォア・インダストリ研究所) です．
*1 現ロシア・カリーニングラード

1

当時の街の様子 (Wikipedia より引用)
当時，偉大な数学者であったレオンハルト・オイラーは，ケーニヒスベルグの橋の問題を次のような問題に置き換えました．
問題 1.1. 次の（図 1）のような点と線からなる図形を考える．この図形を一筆書きすることはできるか？（但し，一筆書きする際の始点と終点は同じとする．
）

図１
つまり，ケーニヒスべルグの街の川で分断された４つの地点を点に置き換え，川にかかっている橋を線に置き換えたわけです．すると，上の（問題 1.1）とケーニヒスベルグの橋の問題が全く同じ問題であることが見て取れると思います．“一筆書き”というと，書き始める地点と書き終わる地点が同じであることを仮定しない
ことが一般的かもしれませんが，テキストの前半では，話を簡単にするために，一筆書きといったときは常に書き始めの始点と書き終わりの終点は同じであることを仮定することにします．（一般的な一筆書きについては，テキストの後半で扱います．）
上で挙げたような図形の一筆書きの問題は誰でも理解でき，よく小学生へのクイズなどにも使われます．
（問題 1.1）の答えはここではまだ言わないことにして，少し違う例で遊んでみましょう．

2

問題 1.2. 次の（図 2.1），（図 2.2），（図 2.3）の図形は一筆書きできるか？

図 2.1

図 2.2

図 2.3

（図 2.1）の図形が一筆書きできることは，少し考えれば分かるでしょう．実際，次の（図 3）のように線をたどってゆけば一筆書きすることができます．

図3
では，（図 2.2）や（図 2.3）についてはどうでしょうか？しばらく時間を掛けて色々と試してみると，これらの図形は “どうも一筆書きできそうにない”ことが感覚的に分かるのではないかと思います．しかし，「（図2.2）が一筆書きできないことを証明せよ」といわれた時，どうやって証明すれば良いのでしょうか？
もちろん，（図 2.2）や（図 2.3）のような小さな図形の場合には，時間を掛けて全てのパターンを試してやれば一筆書きできるかできないかを判断することはできます．しかし，たとえば，次の（図 4）のような複雑な図形が与えられた時，一筆書きできるかできないかをどうやって判断すればよいのでしょう？また，もし一筆書きできるとして，どの順番で線を引けば一筆書きができるのでしょうか？

3

図4
このような問題を考えていると，次のような疑問が自然に浮かんできます．
問題 1.3. 点と線からなる図形が与えられたとき，その図形が一筆書き可能か不可能かを判定する上手い方法
はないか？
オイラーは図形が一筆書き可能か不可能かを判定する素晴らしく簡単な方法を発見しました．それがどのような方法かはこのテキストの第３章と第５章で述べることにして，次の章で数学的なことについて色々な準備をすることにします．

2 問題を考える為の数学的な枠組みを用意する
前の章で紹介したように，数学の問題の中にも，実生活の中での素朴な疑問や問題から生まれたものがたく
さんあります．しかし，一般に日常で使われる言葉は，数学的に見るととても “あいまい”であったり “直感的”であったりすることが多く，そのままでは数学の問題として捉える事はできません．数学として扱う為には，問題のあいまいな所や直感的に書かれている所を数学の言葉に書き直す，ということを行う必要があります．
では，実際に先ほどの一筆書きの問題を考えましょう．前の章で挙げた（問題 1.3）の場合，どこが数学的に明確でないのでしょうか？この問題において明確でない点は三つあります．

(１) “点と線からなる図形”とは何を指すのか？
(２）“一筆書き可能”とは何を指すのか？
(３）“判定する”とはどういうことか？
どれも直感的には容易に理解することができるものなので，どこが明確でないのだろうか？と思うかもしれま
せん．しかし，数学というものは（大雑把に言えば）“数や式”の学問です．よって，数学として捉える為には，上に挙げた（１）〜（３）を文字式や記号を使って定義する（書き直してやる）必要があるのです．それでは，
これら（１）〜（３）を，順番に数学の言葉に書き直してやりましょう．

2.1 点と線からなる図形とは何か
始めに先程の問題点（１）の “点と線からなる図形”を数学的に定義してみましょう．点と線からなる図形，というのは数学的に述べると “グラフ”と呼ばれるものになります．グラフと聞くと，社会科などに現れる棒
グラフや円グラフまたは関数を図にかいたときのグラフのことを連想するかもしれませんが，このテキストで扱うグラフは全く別の物です．
先ず，幾つか数学の用語を準備します．ものの集まりのことを “集合”と呼びます．例えば次のような A や

B や C は集合になります．
A = {1, 2, 3, 5, 7}
B = {a, b, c, d}
C = {a, 3, b, d, 7}: 数字の集まり: 文字の集まり: 文字と数字の集まり

集合といったときには，{1, a, 2, a} のように重複する元を持たないこととします．集合に入っているものをそ4

の集合の元と呼びます．例えば上の例では，1 という数字は A の元ですが B や C の元ではありません．文字a は B や C の元ですが A の元ではありません．あるもの x が集合 X の元である時，x ∈ X と書きます．逆に，あるもの x が X の元ではないとき，x ̸∈ X と書きます．たとえば，先程の集合 A の場合，1 ∈ A であり，また a ̸∈ A です．
集合 X と Y が与えられ，「どの Y の元も X の元である」という条件が成り立つとき，Y は X の部分集合であるといいます．特に，Y の元の数が k 個のとき Y を X の k 元部分集合と呼びます．たとえば，Y = {1, 2, 7}
は X = {1, 2, 3, 5, 7} の 3 元部分集合です．集合 X が有限個の元しか持たない時，X は有限集合であるといいいます．上で挙げた例は全て有限集合ですが，たとえば自然数全体からなる集合 N = {0, 1, 2, · · · } などは有限集合ではありません．このテキストでは，基本的に有限集合しか扱わないので，無限集合については忘れてもらってもかまいません．
言葉で書くと少し分かりにくいかもしれませんが，“部分集合の集合”というものを考える事もできます．たとえば，集合 X = {1, 2, 3, 5, 7} を考えるとき，{1, 2} や {3, 7} や {2, 3, 5} は X の部分集合です．このとき，

Z = {{1, 2}, {3, 7}, {2, 3, 5}}という，X の部分集合達 {1, 2}，{3, 7}，{2, 3, 5} を元とする集合 Z を考える事ができます．このことを踏まえて次の定義を読んでください．
定義 2.1. 有限集合 V と V の２元部分集合からなる集合 E のペア G = (V, E) をグラフと呼ぶ．
また，G = (V, E) がグラフであるとき，V の元を G の頂点，E の元を G の辺と呼び，さらに，V を G の頂点集合，E を G の辺集合と呼ぶ．
上の書き方では，何故これが “点と線からなる図形”を表すのか分かり難いと思いますので，少し例を挙げておきましょう．たとえばV = {1, 2, 3, 4},
E = {{1, 2}, {2, 3}, {3, 4}}とすると，V は有限集合で E は V の 2 元部分集合の集合です．よって，

G = (V, E) = ({1, 2, 3, 4}, {{1, 2}, {2, 3}, {3, 4}})はグラフです．G から次の要領で平面上の図形を作る事ができます：[１] 平面上に V の元で番号付けした点を適当に配置．
[２] 各 E の元 {i, j} に対して，i に対応する点と j に対応する点を線で結ぶ．

図５5つまり，V の元が図形の点を表し，E の元がどの点とどの点が結ばれているかを表します．上の操作によりグラフから点と線からなる図形を作る事ができますが，逆の操作を行うことで，図形からグラフを作る事もできます．また，上の例では数字を元に持つ頂点集合を使ってグラフを作りましたが，必ずしも数字を使う必要はなく，たとえば，G = ({a, b, c, d}, {{a, b}, {b, c}, {c, d}})としても構いません．一般的には頂点集合は V = {v1 , v2 , . . . , vn } などと書かれることが多いです．

[注意] （定義 2.1）で定義したグラフは，実は “単純グラフ”と呼ばれる特別なグラフで，全ての点と線からなる図形に対応しているわけではありません．たとえば，（図 1）のような図形は（定義 2.1）の形では書けません．実際，単純グラフからできる図形は「二つの点の間を結ぶ線は一本しかない」という条件を付けた図形になります．（図 1）の図形も含む形でグラフを定義することもできるのですが，その場合はすこし記号が煩雑になりますので，このテキストでは単純グラフに話を絞りたいと思います．ただ，一筆書きの問題を考える際には，次の（図 6）のように，「二つの点を結ぶ線が二本以上ある時は真ん中に一つ新しい点を作る」という操作をしてやれば単純グラフが得られるので，問題を本質的に変えることはありま
せん．

図6

2.2 一筆書き可能とはどういうことか
今度は “一筆書き可能”ということを，先程のグラフの言葉を使って定義してみましょう．ところで，文字 “二” のように，繋がっていない図形を一筆書きすることはできませんから，図形が一筆書き可能であるためには，少なくとも “繋がっている図形” でなければなりません．先ず，“繋がっているグラフ” というものを定義したいと思います．

G = (V, E) をグラフとします．G の頂点の列*2(v1 , v2 , v3 , . . . , vℓ−1 , vℓ )が条件

*2 列といったときには，順番を考慮します．たとえば (a, b, c) と (a, c, b) は別のものだと思います．

6

「全ての k に対し {vk , vk+1 } は G の辺である（つまり {vk , vk+1 } ∈ E ）」を満たすとき，この頂点の列 (v1 , v2 , v3 , . . . , vℓ−1 , vℓ ) を G の長さ ℓ の歩道と呼び，頂点 v1 をこの歩道の始点，頂点 vℓ をこの歩道の終点と呼びます．特に，始点と終点が一致している歩道，つまり，v1 = vℓ となる歩道を G の閉歩道と呼びます．
実際の図形との対応を分かりやすくする為に，以後，歩道 (v1 , v2 , v3 , . . . , vℓ−1 , vℓ ) のことを

v1 → v2 → v3 → · · · → vℓ−1 → vℓと書くことにします．歩道が図形の上でどのような意味を持つのかを少し見てみましょう．グラフ G = (V, E)
を

V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 6}, {2, 3}, {2, 4}, {2, 6}, {3, 4}, {4, 5}, {4, 6}, {5, 6}}
で定めます．絵に描いてみると，次の（図 7）の左の図ように（図 2.1）と同じ図形になります．

図7
このとき，頂点の列

1→2→4→6→2
は歩道になりますが，これは“頂点 1 から出発して，頂点 2，4，6 へと動いて，また頂点 2 へ戻る道筋”と同一視できます．つまり，頂点 1 から出発して，（図 7）の右の絵のような順路で頂点 2 まで歩いていったときの道のり，と思えば理解しやすいのではないかと思います．（閉歩道の場合は，さらに，“元に戻ってくる”という条件が付きます．）
では，“繋がっている図形”をグラフの言葉で定義してみましょう．“繋がっているということは “図形のどの二点間も結ぶ事ができる”というふうに言い換えることができます．グラフの言葉を使うと “二点間を結ぶことができる”ということは，“二つの点の間に歩道を作ることができる”と言い換えることができますから，
グラフ G = (V, E) が繋がっている図形であるということを「V から任意に二つの頂点 v, v ′ ∈ V を取ってきたとき，v と v ′ を結ぶ歩道が必ず存在する」という条件で定義する事ができます．この条件を満たすグラフの事を “連結グラフ”と呼びます．きちんと定義すると次のようになります．
定義 2.2. G = (V, E) をグラフとする．任意の G の二頂点 v, v ′ ∈ V に対し，必ず v を始点とし v ′ を終点とする G の歩道

v = v1 → v2 → v3 → · · · → vℓ−1 → vℓ = v ′7

が存在するとき，G = (V, E) を連結グラフと呼ぶ．
次に “一筆書き”の定義をしましょう．これも，先程と同じようなアイデアで定義することができます．一
筆書きというのは，始点と終点が一致する歩道（つまり，閉歩道）である特殊な性質を満たすもの，とみることができます．実際，「グラフ G = (V, E) が一筆書き可能である」ということを「E の全ての辺をちょうど一回ずつ使うような閉歩道が存在する」，という条件で定義すれば，これが一筆書きに一致します．このような一筆書きができるグラフを，偉大なるレオンハルト・オイラーの名前を取って，“オイラーグラフ”と呼びます．もう少しきちんと述べると次のようになります
定義 2.3. グラフ G = (V, E) がオイラーグラフであるとは，以下の２条件 (a) と (b) を満たす閉歩道

v1 → v2 → v3 → · · · → vℓ−1 → vℓ = v1が存在するときに言う．（閉歩道なので v1 = vℓ の条件が付く事に注意．）(a) k ̸= k ′ なら {vk , vk+1 } ̸= {vk′ , vk′ +1 }*3 ．
(b) 任意の辺 {i, j} ∈ E に対し，{i, j} = {vk , vk+1 } となる k が存在する．
また，特に，上の条件 (a), (b) を満たす閉歩道をグラフ G のオイラー小道と呼ぶ．
一つ目の条件 (a) が “各辺を一回しかつかわない”という条件に対応し，後の条件 (b) が “全ての辺を使う”という条件に対応するので，二つの条件を合わせると，“すべての辺をちょうど一回ずつ使う”という条件になるわけです．

2.3 判定するとはどういうことか最後に，“判定する”ということを数学的に定義してみましょう．これは，前の二つと違って，少し論理学的な考察が必要となります．ここで少し，命題や必要条件・十分条件といった事項について簡単に復習しておきます．

“命題”とは何かという事をきちんと説明すると，論理学の難しい話になってしまいますので，ここでは簡単にだけ述べておきます．大雑把に言うと，命題とは，“正しいか正しくないかが判定できる文章”のことです．
『空は青い』とか『雲は白い』といったものも一応，命題になるのですが，数学で扱うのは『1 + 1 は 2 である』
とか，『二つの奇数の和は偶数である』といった数学に関係あるものだけです．特に，数学の命題の多くは『ＡならばＢ』という文章構造をしています．たとえば，『二つの奇数の和は偶数である』という命題は『（x と yが奇数である）ならば（x + y は偶数である）』と書き直せます．
では，ここで次のような（命題 P ）を考えましょう．
（命題 P ）
： 『ＡならばＢ』
上の（命題 P ）が正しいとき，ＡはＢが成り立つ為の十分条件であるといいます．また，（命題 P ）の逆の命題（命題 P ′ ）： 『ＢならばＡ』
を考える事ができますが，（命題 P ′ ）が正しいとき，ＡはＢが成り立つ為の必要条件であるといいます．さら*3 集合を考える際には元の並べ方は考慮しませんので {vk , vk+1 } と {vk+1 , vk } は同じものとみなします．

8

に，（命題 P ）とその逆（命題 P ′ ）がどちらも正しいとき，ＡはＢが成り立つ為の必要十分条件であるといいます．
さて，では，一筆書きの問題に戻りましょう．我々が考えたいのは，“図形が一筆書き可能かどうかを上手く判定する” を，数学的に言い換える事です．ここで，“上手く判定する”ということは，“上手い判定条件を与える” と言い換えても良いはずです．判定する事の意味を考えてみれば，“判定条件を与える” ということ
は，次の二つを満たす（条件Ｘ）を与える，と言い換えることが出来ます．

( ＊)『(グラフ G が条件 X を満たす) ならば (G はオイラーグラフである)』『(グラフ G が条件 X を満たさない) ならば（G はオイラーグラフではない）』

上の（＊）を満たす（条件 X）が見つかれば，グラフがオイラーグラフであるかどうかの判定条件を見つけることができた！ということができます．
実は，上の（＊）を満たす条件を見つけることは，必要十分条件を見つけることと同じになります．何故でしょうか？これを見る為には，命題の対偶を考える必要があります．一般に，（命題 P ）
： 『ＡならばＢ』があったとき，次の命題（命題 P ′′ ）： 『ＢでないならばＡでない』
を（命題 P ) の対偶と呼びます．よく知られているように，（命題 P ）とその対偶（命題 P ′′ ）は同値な命題です．つまり，（命題 P ）が正しいなら（命題 P ′′ ）も正しく，逆に，（命題 P ′′ ）が正しいなら（命題 P ）も正し
いことになります．ところで，ＡはＢが成り立つ為の必要十分条件である，とは『ＡならばＢ』『ＢならばＡ』という二つの命題が成り立つことでした．ここで，後半の命題の対偶を考えてやると，上の二つの条件は(＊＊)

『ＡならばＢ』『ＡでないならばＢでない』という形に書き換えることができます．ここで，Ａの所に (グラフ G が条件 X を満たす) という条件を入れ，Ｂに (G はオイラーグラフである) という条件を入れてやれば，上の（＊＊）と（＊）が同じになることが分かると思います．
つまり，“図形が一筆書き可能かどうか判定する方法を探す”，ということは “グラフ G がオイラーグラフであるための必要十分条件を探す”，という形に言い換えることが出来ます．
最後に今までのことをまとめておきましょう．もともと考えていた問題は，（問題 1.3）の “点と線からなる図形が与えられたとき，その図形が一筆書き可能か不可能かを判定する上手い方法はないか？” と言う問題でしたが，これは，今まで（１）〜（３）で見てきたことを使うと，次のような問題に言い換えることができます．
問題 2.4. G = (V, E) をグラフとする．G がオイラーグラフであるための（良い）必要十分条件を与えよ．

9

補足. この章で “点と線からなる図形” というものを “グラフ”という集合の言葉で書き直しました．しかし，
何故そのようなことをするのでしょうか？実際，“有限集合とその２元部分集合の組” と言われるより，“点と線からなる図形” と言った方がずっとわかりやすく感じると思います．
集合の言葉で書くメリットは二つあります．一つは，集合の言葉で書く事により，証明や議論が明快になる
点です．後半のテキストで例を出しますが，数学においては，少し議論を間違えると “明らかに正しくない事が正しいと証明できてしまう” ことがしばしばあります．ですので，数学の証明をするときには，我々は（神経質なぐらいに）議論が正確であるかどうかを気にします．そのような時，たとえば，「図形が繋がっている」というより「任意の二点 v, v ′ ∈ V に対し v を始点，v ′ を終点とする歩道が存在する」と言った方が議論が正確であるのは明らかでしょう．
もう一つのメリットは，集合だと思う事により，適応範囲が広がるという点が挙げられます．たとえば，グラフ理論における有名な定理に “四色定理”と呼ばれる定理があります．これは，四色定理. いかなる地図も，隣接する領域が異なる色となるように塗り分けるには，4 色あれば十分である．
と い う 定 理 で す ．し か し ，こ の 定 理 の ど こ が グ ラ フ の 定 理 な の で し ょ う か ？ 地 図 の 各 領 域 に 対 し ，

A1 , A2 , . . . , An と番号をふってやり，頂点集合 V を V = {A1 , . . . , An } と定めてやります．さらに，辺集
合EをE = {{Ai , Aj } : 領域 Ai と Aj は隣接する }で定めてやりましょう．すると，G = (V, E) はグラフになります*4 ．このとき，領域を色で塗ることと，Gの頂点を色で塗ることが同じことになり，4 色定理をグラフの問題として扱う事ができることになるのです．
（詳細は省きます．どうやってグラフの言葉で定義すれば良いかは，是非，自分で考えてみてください．
）

3 実験・検証・予想
この章では数学の定理がどのような試行錯誤の下で作られるのかを見てみたいと思います．一般に，自然科学について何か研究が行われるときは，大抵
実験 ⇒ 予想 ⇒ 予想の検証という手順を繰り返します．これは数学の場合にも同じ事がいえます．数学の実験とは何か？と思われるかもしれませんが，実験＝具体例の計算，と思っていただければよいかと思います．つまり，数学の研究をすると
きは(1) たくさんの具体例を計算し，(2) こういうことが成り立つのではないか？という予想を立て，(3) 立てた予想が本当に正しいのかどうかを検証するという手順を繰り返します．では，以下で，一筆書きの問題の場合に (1)〜(3) の手順が具体的にどのように進むのかをみてみたいと思います．

*4 各領域は川で隔てられており，それぞれに一本の橋がかけられていると思うと分かりやすいかもしれません．

10

さて，我々が解決したいのは（問題 2.4）ですが，今の段階では，何をどうすればよいのか何も分かりません．このような場合は，とりあえず，幾つかの具体例を考えてみることから始めます．せっかくなので，ここで第１章で紹介したケーニヒスベルグの街のグラフが一筆書きできるかどうかを考えてみましょう．（もし，まだ，ケーニヒスベルグの問題の答えを自分で考えていないなら，この先を読む前に自分なりの回答を用意しておく事をお勧めします．）

図8（問題 1.1）で考えた（図 1）のグラフ（に（図 6）の要領で点を加えたもの）に，前のページの（図 8）ように頂点にＡ〜Ｆまで番号を付けたものを “ケーニヒスベルググラフ”と呼ぶ事にします．ケーニヒスベルググ
ラフはオイラーグラフでしょうか？
先ず，地点Ａからスタートして，一筆書きをして戻って来ることができるかを考えましょう．実はこれは不可能である事が分かります．Ａ地点からスタートした時，一筆書きを完成させる為には，一度Ａ地点に戻ってくる必要があります．しかし，Ａ地点から出ている辺は３本ありますので，一度目にＡ地点に戻ってきた時点
では（Ａから出ている辺を二つしか使っていないので）一筆書きは完成しません．すると，「始めにＡ地点から出発し」，「一旦Ａ地点に戻って」，「もう一度Ａ地点から出発する」という３つの行程が必要であることが分かります．ところで，一筆書きを完成させる為には最後にもう一度Ａ地点に戻ってこなければいけません．しかし，上の３つの行程でＡ地点から出ている全ての辺を使い切ってしまうので，もう一度Ａ地点に戻ってくる
ことは出来ません．よって，Ａ地点からスタートして一筆書きを完成させることは出来ない，ということがわ
かります．
Ｃ地点やＤ地点についても，そこから出ている辺は３本ですから，先程と同じ理由から，Ｃ地点やＤ地点からスタートしても一筆書きすることはできない，ということが分かります．では，Ｂ地点についてはどうでしょうか？Ｂ地点から出発して一筆書きできるとすると，やはり，１．始めにＢを出発し，２．一旦Ｂに戻り，３．もう一度Ｂを出発し，４．さらにもう一度Ｂに戻り，５．もう一度Ｂから出発する，という行程が必要になりますが，この 5 つの行程でＢと繋がっている全ての辺を使い切ってしまうので，やはり最後に戻ってくることができなくなります．よって，Ｂ地点からスタートして一筆書きすることもできないことがわかります．（下の（図 9）も参考にして下さい．
）

11

図9
さて，あとは，Ｅ地点またはＦ地点から出発して一筆書きができるか，という問題が残っていますが，ここで冷静に考えてみると，ＥやＦの点は便宜上付け加えた点なので，（元の（図 1）に戻れば) これらの点は無視してもよいはずです．よって，「ケーニヒスベルググラフは一筆書きできない」，ということがわかりました．
さて，先の議論では “一つの頂点から出ている辺の数” が重要な役割を果たしました．一般にグラフ

G = (V, E) があったとき，頂点 v ∈ V と繋がっている辺の個数をその頂点の次数と言います．たとえば，
ケーニヒスベルググラフにおいて，点Ａ，Ｂ，Ｃ，Ｄの次数はそれぞれ 3，5，3，3 です．きちんと定義すると次のようになります．
定義 3.1. G = (V, E) をグラフとし，v ∈ V を G の頂点とする．v の次数 (deg v と書く) とは次の式で定義される整数のことである

deg v = #{{i, j} ∈ E : v ∈ {i, j}}.
（#X で集合 X に入っている元の個数を表すとする．）
先程議論したことから「一筆書きして戻ってくるとき，一筆書きの始点から出ている辺の数は３本や５本ではない」ということがわかります．このことを数学的にきちんと述べると，次のようになります．
定理 3.2. G = (V, E) をオイラーグラフとする．G の閉歩道

v1 → v2 → · · · → vℓ = v1
が G のオイラー小道なら，deg v1 ̸= 3, 5 である．
上の定理はオイラー小道についての定理ですが，もし，全ての頂点の次数が 3 または 5 であるなら，どの点からスタートしてもオイラー小道を作ることができないことがわかります．ここから，次のようなオイラーグ
ラフについての定理を得る事が出来ます．
定理 3.3. G = (V, E) を連結グラフとする．G の全ての頂点の次数が 3 または 5 であるならば G はオイラーグラフでない．
さて，すると，「G の全ての頂点の次数が 3 または 5 である」という条件は，「グラフ G がオイラーグラフでない」という条件の十分条件を与えている事になります．これは必要十分でしょうか？実は，簡単に上の定理を上回る定理を作る事ができるので，これは必要十分ではありません．実際，ちょっと感の良い人なら，（定理 3.2）や（定理 3.3）は 3 や 5 だけでなく，7, 9, 11 といった数でも成り立つ事，つまり，「v1 の次数は奇数ではない」，という事を発見できるでしょう．実際に，次の定理が成り立ちます．

12

定理 3.4. G = (V, E) をオイラーグラフとする．G の閉歩道

v1 → v2 → · · · → vℓ = v1
が G のオイラー小道なら，deg v1 は偶数である．
実際，

v1 → v2 → · · · → vℓ = v1
が G のオイラー小道であるならば，一筆書きをする際に頂点 v1 から出て行く回数 = 頂点 v1 に入る回数が成り立ち，v1 を含む辺の数が偶数である事が分かります．
ところで，先程の（定理 3.3）と同様に，（定理 3.4）から次の定理が導かれます．
定理 3.5. G = (V, E) を連結グラフとする．G の全ての頂点の次数が奇数であるなら G はオイラーグラフでない．
さて，では上の条件は必要十分条件になるでしょうか？先程と違って，少なくとも，上の定理を上回るような定理をすぐには作れそうにありません．ですので，次のような予想を立ててみる事にします．
予想 3.6. G = (V, E) を連結グラフとする．G がオイラーグラフでないことの必要十分条件は，G のどの頂点の次数も奇数であることである．
さて，では，上の予想が正しいのかどうかを検証してみましょう．つまり，本当に『オイラーグラフでないならばどの頂点の次数も奇数』という命題が正しいのかどうかをチェックしてみましょう．
ここで，１章に出てきた（図 2.2）と（図 2.3）を考えましょう．我々の予測では，これらはオイラーグラ
フではないはずでした．しかし（図 2.2）をみてみると，（図 2.2）の真中の点の次数は 4 です，つまり，オイ
ラーグラフではないが，次数が偶数である点を持ってしまうことになります．ということは，先程考えた（予想 3.6）は正しくない，という事が分かってしまったことになります．
残念ながら，先程考えた（予想 3.6）は正しくなかったわけですが，これで話が振り出しに戻ったのかというと，そういうわけではありません．なぜなら，我々は “頂点の次数”が何かオイラーグラフと関係がありそうだ，という事を知ったからです．それでは，今までみてきたグラフについて，その頂点の次数がどうなっているかを調べてみましょう．まとめると次のようになる事が分かります．
頂点の次数オイラーグラフか？

図1

3,5,3,3

オイラーグラフでない

図 2.1

2,4,2,4,2,4

オイラーグラフ

図 2.2

3,3,3,3,4

オイラーグラフでない

図 2.3

3,3,3,3,3,3,3,7

オイラーグラフでない

オイラーグラフである場合と，オイラーグラフでない場合で，頂点の次数について何が違うのでしょうか？
明らかな差として，「オイラーグラフである場合は全ての頂点の次数が偶数である」ということが見て取れます．すると，今度は次のような予想を立てることができます．

13

予想 3.7. G = (V, E) を連結グラフとする．G がオイラーグラフであることの必要十分条件は，G のどの頂点の次数も偶数であることである．
ではこの（予想 3.7）が正しいかどうかを検証してみましょう．
（結論から言うと，この予想は正しいことが分かります．）上の予想が正しいとすると，『G がオイラーグラフであるならば G のどの頂点の次数も偶数である』という命題が正しいはずです．本当にこのようなことが成り立つのでしょうか？

G がオイラーグラフであるとしましょう．すると，G のオイラー小道
v1 → v2 → · · · → vℓ = v1が存在します．（定理 3.4）から，少なくとも頂点 v1 の次数は偶数である事が分かります．では，v1 以外の点についてはどうでしょうか？実は，他の頂点の次数も偶数であることが，次の簡単な定理から分かります．
定理 3.8. G = (V, E) をオイラーグラフとする．閉歩道

v1 → v2 → · · · → vℓ = v1
がオイラー小道なら，

v2 → v3 → · · · → vℓ = v1 → v2
もオイラー小道である．
上の（定理 3.8）は明らかなので，証明はしないことにしますが（下記の（図 10）をイメージしてください），（定理 3.8）を認めると，頂点 v1 を始点とするオイラー小道があったとき，頂点 v2 を始点とするオイラー小道が作れることが分かります．さらに，（定理 3.8）を何度も使うことで，G のどの点を始点にしても良いことが分かります．我々は，オイラー小道の始点の次数が偶数になることを既に知っていますので，オイラーグラフのどの頂点の次数も偶数になることが証明できたことになります．

図 10
さて，とにかく，これで次の定理が証明できた事になります．
定理 3.9. G = (V, E) を連結グラフとする．G がオイラーグラフであるならば，G のどの頂点の次数も偶数である．
上の定理は，『G のどの頂点の次数も偶数である』という条件が『G がオイラーグラフである』ことの必要条件であることを示しています．（予想 3.7）が正しい事を示すには，条件の十分性，つまり，『G のどの頂点の次数も偶数であるならば G はオイラーグラフである』という命題を証明する必要があるのですが，この命

14

題の証明には背理法や帰納法のテクニックが必要になりますので，証明について詳しく述べる後の章で扱う事にします．
証明は一部後回しにしましたが，これで（予想 3.7）が正しいことがわかりました．つまり，次の定理が得られたことになります．
（この定理はオイラーの一筆書き定理と呼ばれます．
）
オイラーの一筆書き定理. G = (V, E) を連結グラフとする．G がオイラーグラフであるための必要十分条件
は，G のどの頂点の次数も偶数であることである．
この定理はグラフがオイラーグラフであるかどうかのとても簡単な判定方法を与えてくれます．例えば，第一章に出てきた（図 4）の図形を考えて下さい．この図形の頂点の次数は全て偶数ですから，オイラーの定理
から（図 4）は一筆書き可能であることがたちどころにわかってしまいます．
さて，最後に，ここまでの理論的な流れを理解できているかをチェックする為，演習問題を一つ挙げておきます．
問題 3.10. これまでテキストでは，始点と終点が同じであるような一筆書きのみを考えてきた．始点と終点が必ずしも一致しないような一筆書きについて考える．

(1) 図形が (必ずしも始点と終点が一致しない) 一筆書き可能であることを，（定義 2.3）に習って，グラフの言葉を使って定義せよ．

(2) グラフが一筆書き可能であるとき，次数が奇数となる頂点の個数は 0 個もしくは 2 個である事を示せ．

補足. この章では「オイラーグラフの頂点の次数は偶数になる」ということを見ました．この事実自体は，とても簡単に証明できる事なので（たとえば，とある教科書には「このことは自明である」とだけ書いてあります），この章を読んで，ずいぶんまわりくどい説明をしている，と感じられた方もいると思います．ただ，この章で伝えたかったことは，「何故オイラーグラフの頂点の次数が偶数になるか」ではなく，「どのような考え
で，そのような条件を思いつくに至ったのか」ということです．このことが多少なりとも伝わっていれば幸いです．

4 証明の道具講座の前半では，与えられたグラフが一筆書き可能であるかどうかの判定を，オイラーの一筆書き定理という形で定式化しました．後半では，この定理の証明を２通り紹介したいと思いますが，それぞれ，背理法，数学的帰納法という二大証明テクニックを用いますので，まずそれらの復習も兼ねて，色々な例を見てみたいと思います．

4.1 背理法
命題 P を示したい時に，• P の否定を仮定すると，矛盾が生じるとして証明する方法が，背理法です．この手法の起源は大変古く，例えば古代ギリシャの数学者ユークリッド

15

は，背理法を用いて次のような定理を示しました．
定理 4.1. 素数は無限に多く存在する．

Proof. 素 数 が 有 限 個 し か 無 い と 仮 定 す る ．そ れ ら を p1 , p2 , . . . pn と す る と ，N = p1 p2 · · · pn + 1 は
p1 , p2 , . . . pn のどれで割っても 1 余る．N が素数ならば，p1 , p2 , . . . pn のどれかと一致しなければならな
いが，これは不可能であり，N が素数でないならば，p1 , p2 , . . . pn 以外の素因数を持つことになる．これは矛盾であるから，素数は無限に多く存在する．
注意: この証明は，必ずしも N が素数であることを示してはいません．例えば，2 · 3 · 5 · 7 · 11 · 13 + 1 = 59 · 509となります．
背理法は直接的ではないため，証明すべき命題が複雑になると，どの様に適用して良いかわかりにくくなる
ことがあります．例えば，「A ならば，B かつ C 」という命題を背理法で示そうとする場合，「A かつ，B でないか C でない」を仮定して矛盾を導くという議論になります．また，句点の位置を変えただけの「A ならば B ，かつ C 」を示す場合は，「C が成り立たないか，A が成り立ち B が成り立たない」を仮定して矛盾を導くことになります．この様に否定が関わってくると論理は複雑になるのですが，試しに次の様なパズルを考えてみて下さい．
例 4.2. 表には 1 から 4 までの数字，裏は赤か青で塗られた 4 枚のカードが，机の上に並べられている．今，「1,2, 青, 赤」が上に向けられているする．この時，なるべく少ないカードをめくってみて，「奇数のカードの裏は赤い」という命題を確かめるには，どのカードをめくってみればよいか．
また，「全ての」や「存在する」という形の命題の否定を作るときには，少し注意が必要です．試しに，次の問題を考えてみてください．
例 4.3. 自然数 a, b, c が，a2 + b2 = c2 を満たすとき，a, b, c の中には少なくとも一つ 3 の倍数が存在する事を，背理法で示せ．
背理法の誤った適用例も見ておきます．
例 4.4. 0 = 1 であることを背理法で示す．0 ̸= 1 であると仮定する．この両辺に 0 をかけると 0 ̸= 0 となる
が，これは矛盾である．よって背理法により 0 = 1 が示された．
補足 1. ところで，背理法を用いた証明はなぜ正しいのでしょうか．残念ながら，この問にはある意味で数学
は答えることができません．数学では，「証明とは，背理法や三段論法など決められたルールを繰り返して得られる文章」として証明を “定義” しています．ですから，背理法は「この決められたルールにのっとっているから正しい」と数学ではみなします．実は，数学の世界には背理法を許さない証明体系を考えている人たちもいて，直観主義論理と呼ばれています．
例えば，うそつきのパラドックスとしてよく知られた次のような命題を考えてみましょう:

P : 「命題 P は偽である」
これを背理法で “証明” しようとしてみます: 命題 P が偽であると仮定すると，命題 P の主張より，命題 Pは真になり，これは命題 P が偽であるという仮定に矛盾する．よって背理法により，命題 P は真である．
しかしもう一方で，命題 P を真だとしてもやはり矛盾が出てくるので，上の主張は正しくありません．こ16

の様に，無制限に命題の形や背理法を扱おうとすると論理は破綻してしまうのです．それを回避しようとする
努力の一つが，直観主義論理です．
背理法による証明は鮮やかである一方，何か狐につままれたような，本当に証明できたのか，論理を弄んでいるだけのような気がします．この様な長所と短所については，後にもう少しはっきりさせようと思います．

4.2 数学的帰納法
自然数に関するある命題 P (n)，例えば，

1 + 2 + ··· + n =

n
∑

i=

i=1

n(n + 1)2を示したい時に，

1. n = 1 の時，P (1) は正しい
2. n = k の時，P (k) が正しい事を仮定すると，P (k + 1) も正しいという二つのステップを通して証明する方法が，数学的帰納法の一番典型的な形でしょう．数学的帰納法を用いたい場合には，まず示すべき命題がきちんと分かっている (予想ができている) 必要がありますが，その様な場合には証明のための非常に強力な手段となります．
オイラーの定理を証明するにあたっては，数学的帰納法の標準的な形から多少変形した議論を用いますから，ついでにここで色々なバリエーションを見ておきたいと思います．
例 4.5 (ハノイの塔). 図の様に大きさの異なる円盤が左端に積み重ねられた状態から始めて，すべてを右端に移動するのが目的というゲームを考えよう．円盤は一度に一枚ずつ移動させるが，その時小さな円盤の上に大きな円盤を乗せることはできない．n 枚の円盤すべてを移動させる事はいつでも可能だろうか．また，最短で何手必要か?

ハノイの塔 (Wikipedia より引用)
例 4.6. 「アミダくじでは，異なる始点から出発すると異なる終点に到達する」事を，横棒の本数に関する帰納法で示せ．ただし，ここでのアミダくじは，次の条件をみたすものとする：• 縦棒は垂直に描かれてており，それぞれの上端を始点，下端を終点とする• 横棒は水平に描かれており，全て高さが異なっている
17

アミダくじ (Wikipedia より引用)
数学的帰納法において，大抵の場合 n = 1 の時は自明でしょう．しかし，時には一見明らかな初期データ
が，非常に重要な意味を持つことがあります．次の様なパズルを考えてみましょう．
例 4.7. ある刑務所には 100 人の囚人が収監されている．元日の朝，それぞれの囚人は赤か青の帽子を本人には分からない様にかぶせられ，釈放をかけたゲームをする為に大広間に集められた．このゲームのルールは次の通りである:• 赤と青の帽子は 50 個ずつであるが，囚人はその事を知らない．また，帽子の色が赤と青しかないことも知らない．

• この部屋には鏡等なく，囚人は自分の帽子の色を見ることはできないが，他の 99 人の帽子の色は見えている．

• 囚人は口をきいたり，他の囚人とコミュニケーションをとってはならない．
• 囚人は自分の帽子の色が分かり，それを論理的に説明できる場合，看守のいる隣の部屋へ行く事ができる．ここで論理的な説明ができれば釈放されるが，そのチャンスは一度きりであり，また，看守の部屋に行くドアの鍵が開くのは毎日正午に限る．看守は沢山いるので，一日に何人にでも同時に対応することができる．

• 囚人達は，誰が看守の部屋へ行ったかは分かるが，看守の部屋の様子は見る事もきくこともできない．
• 全ての囚人は大変賢く，また注意深い．そして，お互いにそのことを知っている．
元日の午前 9 時，看守の次の言葉でゲームが開始された．「この中には少なくとも一人ずつ，青い帽子と赤い帽子をかぶった人間がいる．」
ゲーム開始から丁度 50 日目で全ての囚人が釈放されることになるのだが，その理由を説明せよ．
小さな自然数 n に対する主張から順繰りに，ドミノ倒しのように全ての自然数について主張が証明されてゆくのが，数学的帰納法のミソですが，その出発点は必ずしも n = 1 に限る必要はありません．次の例を考えてみてください．
例 4.8. 「n ≥ 4 の時，2n > n2 − n + 2 を示せ」
与えられた不等式は，n = 1 のときには 1 > 12 − 1 + 2 = 2 となり成立しません．
上で見た数学的帰納法が，直前の結果のみ仮定して証明するのに対し，次のような手順にしても主張を証明できます．

1. n = 1 の時に，P (1) は正しい
2. k 以下の全ての自然数 n に対して P (n) が正しい事を仮定すると，n = k + 1 の時に P (k + 1) は正しい
18

オイラーの定理の証明にはこの形の議論を用いるのですが，まず次の例でその使い方を確認しておきます．
例 4.9. 1 より大きいすべての自然数は，素数の積に (順序を除いて) 一意的に表せることを示せ．ここで「積」
は一つの数の積も許すことにする．つまり，素数は自分自身ひとつの積であるとする．
少し変わった数学的帰納法の亜種としては，次のように大きい自然数から逆に下がってゆく，無限降下法と呼ばれる証明法があります．具体的には，自然数に関する主張 P (n) の否定を示したいとき，• n について P (n) が正しいと仮定すると，n より小さいある自然数 k に関して P (k) が正しい
• 1 より小さい自然数は存在しないので矛盾が起きるという形の証明です．これは，数学的帰納法と背理法を組み合わせた議論になっています．
例 4.10.

x3 + 2y 3 = 4z 3を満たす自然数 x, y, z は存在しないことを示せ．
これまで見てきたように，自然数に関する主張を証明するのに大変強力な数学的帰納法ですが，誤った使い方をしてしまう危険性もあります．次の二つの例は，その典型と言えるでしょう．どこに問題があるのか，よく考えてみてください．
例 4.11. 古代ギリシャ哲学のひとつの成果である「ハゲのパラドックス」では，数学的帰納法を用いて，全ての人間が「ハゲ」であることを “証明” している．その議論は次のとおり:
髪の毛が 1 本しかない人は「ハゲ」である．「ハゲ」である人より，髪の毛が一本だけ多い人はやはり「ハゲ」である．よって，(何本毛があっても) 人類皆「ハゲ」である．
例 4.12. もう一つ，数学的帰納法の誤った適用例として，「一つのクラスには，右利きの生徒もしくは左利きの生徒のどちらかしかいない」という命題の証明も見てみよう．(ここでは両利きの生徒はいないものと仮定します．)
一人しか生徒のいないクラスには，右利きか左利きの生徒しかいない．生徒が k 人いるクラスについては，「右利きか左利きの生徒しかいない」が成り立つと仮定しよう．生徒が k + 1 人いるクラスについて，そのう
ちある一人 a さんを除くと k 人のクラスになるので，仮定により右利きか左利きの生徒しかいない．また，aさん以外の b さんを除いた場合も，やはり仮定より右利きか左利きの生徒しかいないので，a さんも a さん以
外の生徒と同じ利き手である．よって，クラス全員が同じ利き手の生徒である．
補足 2. この様に非常に強力な数学的帰納法ですが，どの様に生まれ，誰が最初に用いたのでしょうか．「ハゲのパラドックス」で紹介したように，その起源ははるか紀元前にさかのぼり，正確には分かっていません
が，数学的帰納法を縦横無尽に駆使して，整数論の様々な結果を得た数学者に，フェルマーがいます．有名な「フェルマーの最終定理」の人で，17 世紀に活躍しました．フェルマーは，数学的帰納法を現在の形に整備したひとりだと言われています．
さて，数学的帰納法を用いた証明は，なぜ数学的な証明として「正しい」のでしょうか．これは決して自明なことではなく，この問に正確に答えるには，自然数とはなにか，について深く考察する必要があります．その一つの回答は，19 世紀末にペアノによって与えられました．簡単に言いますと，「数学的帰納法が成り立つ
様な集合が自然数だ」というものです．ここでも背理法の時と同じく，別の事柄から正しさが論理的に従うも19

のではなく，それ自体を論理の出発点として定義する，という形になっています．数学では，自然数のような自明に，文字通り自然の中に存在していると思われる対象についてさえ，しっかりした定義を与えなくては正確な議論はできないのです．
数学的帰納法による証明は，もともと正しい命題を推測できないと使えない，という難点がある一方で，ひとたび正しい命題が見つかれば，後は機械的に証明を進めることができます．この点については，後で背理法と比較しつつ見てみることにします．

5 オイラーの定理の証明
さていよいよ，オイラーの定理の証明に入りましょう．背理法と数学的帰納法を用いた二通りの証明をしますが，それらには一長一短があります．このことについてはあとで詳しく見ることにします．
まず，オイラーの定理の主張をもう一度確かめておきましょう．ここでは，前半で扱ったものよりも少し強い形の定理を証明します．
定理 5.1. 連結なグラフ G について，次が成り立つ：• 次数が奇数の頂点が 0 個 ⇔ 任意の点を始点かつ終点とする一筆書きが可能• 次数が奇数の頂点が 2 個 ⇔ 次数が奇数の頂点をそれぞれ始点と終点とする一筆書きが可能
以下では “一筆書き” という言葉を使うとき，必ずしも始点と終点が一致していなくても良いものとします．
前半部分で，一筆書きが可能なら次数が奇数の頂点は 0 個または 2 個である事を証明しました．ですから後示すべき事は，逆に次数が奇数の頂点が 0 個または 2 個である時に，始点と終点の条件を満たす様な一筆書きがいつでも存在する事です．

5.1 背理法を用いた証明
まずは背理法を用いた証明をします．
証明 1. まず，G が奇数次数の頂点を持たない場合を考える．G の中で同じ辺を 2 度通らない歩道のうち最も長いものを C とする．G に次数が奇数の頂点がないことから，C は閉歩道となっていることが分かる．ここで，C がすべての辺を通っていれば，G の一筆書きを与えている．
これから，C が全ての辺を通っていることを背理法で示す．もし全ての辺を通っていないと仮定すると，Gが連結であることから，C に接続する C に含まれない辺が存在することになる．この辺を C に付け加えれば，C より長い歩道が得られ，C が最も長い歩道であることに反する．よって背理法により，C が G の一筆書きであることが分かる．C は閉歩道であるから，任意に始点を選べる．

20

次に，G が二つの奇数次数の頂点 P, Q を持つとする．G に，G に含まれない頂点 R と辺 P R, RQ を加えたグラフを G′ とすると，G′ は連結な奇数次数の頂点を持たないグラフとなる．上の議論により，G′ は P を始点かつ終点とする一筆書き C を持つ．C が閉路であることから，必要なら始点と向きを取り替えることで，最後に QR, RP と進んでいるとして良い．C から QR, RP を除くと，P を始点とし Q を終点とする G の一
筆書きが得られる．

5.2 帰納法を用いた証明
次は数学的帰納法を用いて証明してみます．場合分けがあり，少し息の長い議論になりますが，大枠として
は辺の本数に関する数学的帰納法により証明されます．
証明 2. G の辺の本数 n に対して，P (n) を「G の奇数次数の頂点が，0 個なら任意の点を始点かつ終点とす
る一筆書きが可能，2 個ならそれらを始点と終点とする一筆書きが可能」という命題とする．以下，P (n) が任意の自然数 n について成り立つことを帰納法で示す．n = 1 の時，グラフは図のようなものしか無いので明らかに P (n) が成り立つ．

n = k までの自然数について P (n) が成り立つことを仮定する．G を k + 1 本の辺を持つ連結グラフとする．
(1) G に奇数次数の頂点が無い場合，G から任意の辺 P Q を除くと辺の数が n − 1 本であり，二つの奇数次数の頂点 P, Q を持つグラフ G′ が得られる．この時，G′ は連結である．なぜなら，もし G′ が非連結だとす
ると，P を含む成分と Q を含む成分に分かれるが，それぞれの奇数次数の頂点の個数は 1 個になってしまい，
これはありえない (最後の演習問題を参照)．よって帰納法の仮定により，G′ には P を始点とし Q を終点とす
る一筆書きが存在するから，最後に QP を付け加えれば，P を始点かつ終点とする G の一筆書きが得られる．

21

(2) G が二つの奇数次数の頂点 P, Q をもつ場合，P に接続する辺 P R を任意に選んで取り除いたものを G′
とおく．

(2a) まず G′ が連結である時を考える．
R = Q である場合，G′ は奇数次数の頂点を持たないので，帰納法の仮定より Q を始点かつ終点とする一筆書きが存在する．最後に QP を付け加えれば Q を始点とし P を終点とする G の一筆書きが得られる．

R ̸= Q である場合，G′ は二つの奇数次数の頂点 R, Q をもつので，帰納法の仮定より Q を始点とし R を終点とする一筆書きが存在する．最後に RP を付け加えれば Q を始点とし P を終点とする G の一筆書きが得
られる．

(2b) 次に，G′ が非連結の時を考える．
G′ の P を含む連結成分を G1 ，R を含む連結成分を G2 とおく．
R = Q である場合，G1 も G2 も奇数次数の頂点を持たないので，帰納法の仮定よりそれぞれ P, Q を始点
かつ終点とする一筆書きが存在する．これらを P Q でつなげれば P を始点とし Q を終点とする G の一筆書きが得られる．

R ̸= Q である場合，G1 は奇数次数の頂点を持たず，G2 は二つの奇数次数の頂点 R, Q をもつので，帰納法の仮定よりそれぞれ P を始点かつ終点とする一筆書きと，Q を始点とし R を終点とする一筆書きが存在す
る．これらを P Q でつなげれば P を始点とし Q を終点とする G の一筆書きが得られる．
以上により，P (k + 1) が成り立つことが示されたので，数学的帰納法により全ての n について P (n) が成り立つことが証明された．

6 アルゴリズム
オイラーの定理の証明を２通り見てきましたが，これらは単に背理法を使ったか数学的帰納法を使ったかという手法の違いだけでなく，数学的にも本質的に異なった意味をもっています．この章ではそれについて少し考えてみたいと思います．
前章の証明 1 では，与えられたグラフが一筆書き可能かを，一筆書きの存在を背理法を使って示すことで判定していました．短い議論ですむ反面，この証明だけ見ても，与えられたグラフの一筆書きの方法を実際に一つ与えることはできません．この様な証明を存在証明と言います．それに対し，証明 2 の様に，実際に一筆書きの方法を与える様な証明を，構成的証明と呼び，具体的な構成法をアルゴリズムといいます．
構成的証明は実際に解答を作ることができる分，存在証明より有用といえますが，一方で純粋な存在証明の方が構造の本質をとらえ，すっきりと鮮やかな証明になることが多いです．その典型的な例として，n 次方程式の解について取り上げてみましょう．

22

例 6.1 (代数学の基本定理). 複素数 (もちろん実数でも可) を係数とする n (n ≥ 1) 次方程式

xn + an−1 xn−1 + · · · + a1 x + a0 = 0
は複素数の範囲に必ず解を持つ．その個数は重複も込めると丁度 n 個である．
例 6.2 (二次方程式の解の公式). 二次方程式

ax2 + bx + c = 0
は，二つの解−b ±√b2 − 4ac2aを持つ．
代数学の基本定理は，解が存在することは保証しますが，その解がどのような数になるかは何も教えてくれ
ない，存在証明です．対照的に，二次方程式の解の公式は，解を具体的に教えてくれる点では有用ですが，同様に三次・四次と解の公式*5 を作ると非常に複雑となり，また五次以上では (根号等のみを用いた) そもそもその様な公式は作れないこと*6 からも，方程式に関する本質をついたものとは言えません．この例からもわかるように，どちらの形の証明も重要であり，目的によって使い分けられます．
補足 3. 代数学の基本定理を，存在 “証明” だと述べましたが，この定理の証明は高校数学の範囲ではできませんのでここでは扱いません．(一見代数の問題であるように見えますが，実は複素数の幾何的性質，より正確には位相に基づく定理なのです．詳しく知りたい方は，高木貞治著，解析概論 (岩波書店) などを参照されて下さい．) ともかく今は，この定理の証明が解を実際に構成してみせるわけではない事だけ認めて下さい．
背理法を用いた証明は，大抵の場合存在証明になります．ユークリッドによる素数の無限性も，実際に大きい素数を得る方法を教えてくれるわけではありません．
幸いにもオイラーの定理に対しては，前章に見た様に，存在証明だけでなく構成的証明も知られています．
より具体的に一筆書きを与える方法を見る為に，証明 2 をアルゴリズム*7 の形に書き直してみましょう．

Fleury のアルゴリズム. 奇数次数の頂点が存在する場合は任意の奇数次数の頂点から，存在しない場合は任意の頂点からスタートする．頂点から頂点へと辺を伝って動くとき，一度通った辺は順に取り除いてゆく．また，連結する辺がなくなった頂点も取り除く．次に進むべき辺を選ぶとき，その辺を取り除いたグラフが常に連結になっている様にできるので，その様な辺を任意に選んで進むことを繰り返すと，それが一筆書きを与える．
このアルゴリズムが，一筆書き可能なグラフに対してちゃんと一筆書きを与える事は，証明 2 によって保証されるのです．(もし途中で辺を選ぶことができなくなるなら，そもそも一筆書きが不可能なグラフだと言う事になります．) このアルゴリズムの働く様子を，次のグラフで実際に試してみて下さい．

*5 カルダノ・フェラリの公式として知られています．
*6 アーベルとガロアが独立に示しました．
*7 問題の解を具体的に与える手順をアルゴリズムと言います．コンピューターの世界でも良く用いられる用語です．

23

7 拡張
数学において新しい定理を得るために最も頻繁になされる事は，既に知られている定理の適用範囲を広げる
ために，条件を弱めたり設定を変えたりと拡張を施すことです．この様な考え方，もしくはそれにより得られる新しい定理は，一般化と呼ばれます．一般化を考えることは，既存の理論の限界や本質をつかむ事に他ならず，結果として新しい定理が生まれなかったとしても，理論を学ぶ上で非常に重要であり，数学の基本的な学習法と言えると思います．
一つの定理に対して，一般化の方法はもちろんひと通りではありません．ここでは，オイラーの定理の一つの一般化を見てみようと思います．
これまでは辺の向きは考えず，どちらの方向にも進むことができましたが，ここではすべての辺が一方通行であるような状況を考えます．応用上も，展覧会の順路を作る際などはこの様な設定が相応しいでしょう．
定義 7.1 (有向グラフ). 辺に向きが定まっているグラフを，有向グラフと呼ぶ．より正確には，有向グラフにおいて辺とは，二つの点 P, Q ∈ V の順序づけられた対 (P, Q) ∈ V × V である．
また，有向グラフにおいて点 P の次数とは，P を始点に持つ辺の数 − P を終点に持つ辺の数と定める．
有向グラフにおいて歩道は，辺の向きを考慮しなければなりません．直感的な意味は明らかですので，正確な定義は皆さんで考えてみて下さい．
例 7.2. ひらがな全体を頂点集合，文字 P から始まり Q で終わる単語を辺とする有向グラフにおいて，歩道
は「しりとり」にあたる．
有向グラフの設定においても，オイラーの定理の一般化が成り立ちます．
定理 7.3. 連結な有向グラフ G が一筆書き可能である事と次は同値：• 次数が 1 の点を高々一つ，次数が-1 の点を高々一つ持ち，それら以外の点は次数 0 である
証明は向きがない場合と同様ですので省略します．

....................................................................................................
オイラーの定理をもとにして，まだまだ様々な一般化や同種の問題を考えることができますが，他にどの様な展開があるのかについて，いくつか例を列挙しておきます．興味があれば考えてみてください．

24

• 与えられたグラフに対して，一筆書きの方法が全部で何通りあるのかの場合の数を数える• ある数以下の辺 (または頂点) をもつグラフのうち，一筆書き可能なものがどれくらいあるかを調べる•「全ての辺を一度ずつ通る歩道をさがす」という問題を「全ての頂点を一度ずつ通る歩道をさがす」に置き換える (ハミルトン閉路といいます)

8 応用
最後に，オイラーの定理の実用的な応用をいくつか見て終わりにしたいと思います．
例 8.1. コンピューター上で設計された，建築や機械，型紙などの図面データを出力するしたり切り出したりする装置をプロッターという．(電子制御されたアームがペンを動かす様子を想像して下さい) プロッターを使って図面を出力する際，なるべく一筆書きで書き出す方が効率が良い．そこで，与えられた図面データに対して，いくつか辺を加えて，一筆書きにするという事が行われる．付け加えられた部分はペンを浮かせてアームを移動させる．

プロッター
例えば図の様なデータに対しては，オイラーの定理により，点線部分を付け加えれば一筆書きにできる事が分かる．
例 8.2 (ストロー多面体). 図のように，ストローに糸を通して組み上げることで，多面体を作ることを考える．糸は途中で切れずに一つながりで，各々のストローを 2 回ずつ通る様にしたいが可能だろうか．

25

ストロー多面体
この問題に対しては，次のようにしてオイラーの定理が適用できる:• G の頂点を，多面体の頂点とする．
• 多面体の辺に対して，G の二本の辺を対応させる*8• G は連結なグラフであり，辺が “二重化” されていることから奇数次数の頂点を持たないので，オイラーの定理により一筆書きが存在する．

オイラーの定理では，グラフというものを図から離れて抽象的に扱ったため，紙の上に描ける (平面的であるといいます) 事を仮定していません．ですから，上の例からも分かるように，立体の場合にまで適用範囲が広がるのです．

練習問題
1. 黒板に立体図形を書くとき，円錐ならば一筆で書く事ができる．では，三角錐や四角錐等の角錐を黒板に書くとき，一筆で書くことはできるか？また，その理由は何故か？

2. 3 ページ目の（図 2.1）をグラフとして集合の言葉で書くと，9, 10 ページ目に挙げたような集合となる．
（図 2.2）及び（図 2.3）をグラフとして集合の言葉で記述せよ．

3. 連結なグラフにおいて，奇数次数の頂点の個数は必ず偶数個であることを示せ．
4. 漢字の「田」を一筆書き可能にするためには，少なくとも何本の辺を加える必要があるか．また，どの様に加えればよいか．始点と終点が一致する場合と，必ずしも一致しない場合の両方で考えてみよ．

5. §8 で扱った方法で立方体を作りたい．対応するグラフとその一筆書きを与えよ．(ヒント：立方体を含む多面体のグラフはうまく平面に書くことができます．まずはその方法を探してみて下さい．)*8 こうしてできたグラフは単純グラフとはならないが，2.1 章の注意に従うと単純グラフと置き換えることができる．

26

おわりに
この講座を通して，素朴な一筆書きの問題を，グラフという数学的対象を用いて調べるということを行いましたが，グラフ理論は現在では幅広い応用をもつ数学の一分野として確立されています．さらに興味を持たれた方は，本格的な入門書である• R.J. ウィルソン著，グラフ理論入門 (近代科学社)などをお読みになってみてください．または，パズルを通して気楽にグラフ理論を楽しまれてみたい方は，• 根岸生也著，グラフ理論 3 段階 (遊星社)
がお勧めです．中学・高校生にも十分読める様に書かれていますので，自由研究の題材にも良いかと思います．

27