一筆書き

六芒星の一筆書きの例

一筆書き（ひとふでがき）とは、広い意味では「筆記具を平面から一度も離さず線図形を描く」ことである。狭い意味では、これに加えて「同じ線を二度なぞらない（点で交差するのはかまわない）」という条件が加わる。筆記体のdは、前者の意味では一筆書きであるが、後者の意味では一筆書きではない。

以下は後者の狭い意味での一筆書きについて記す。

三角形「△」や四角形「□」は一筆書き可能だが、十字「+」は一筆書きできない。また、五芒星や白星「☆」、六芒星「✡」は一筆書き可能だが、アスタリスク「＊」は一筆書きができない。このように、一筆書きできる図形とできない図形がある。

与えられた図形が一筆書き可能かどうかという問題の例として、「ケーニヒスベルクの橋の問題」（テンプレート:Lang-de-short）が知られている。

ケーニヒスベルクの問題

ブレーゲル川と七つの橋を示したオイラーの時代のケーニヒスベルク
現在のケーニヒスベルクの橋のLink（現在は、橋の本数が過去とは異なる）

18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルク（現ロシア連邦カリーニングラード）という大きな町があった。この町の中央には、プレーゲル川という大きな川が流れており、七つの橋が架けられていた。あるとき町の人が、次のように言った。

「このプレーゲル川に架かっている7つの橋を2度通らずに、全て渡って、元の所に帰ってくることができるか。ただし、どこから出発してもよい」

町の人が言ったことはできるだろうか。

1736年、レオンハルト・オイラーは、この問題を以下のグラフに置き換えて考えた。

このグラフが一筆書き可能であれば、ケーニヒスベルクの橋を全て1度ずつ通って戻ってくるルートが存在することになる。

そして、オイラーは、このグラフが一筆書きできないことを証明し、ケーニヒスベルクの問題を否定的に解決した。

この問題は論理的に考えれば確かに不可能であるが、実は屁理屈気味だが解法が存在している。それは｢源流などを迂回する｣という方法であり、こうすることで経路を一本増やすことができ、解答可能になる。これは問題内容に一切違反していないので正当な回答とみなせるが、一般的ではない。

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。

すべての頂点の次数が偶数 →ある頂点から出発し、元の頂点に戻り、さらにその頂点から出発し、元の頂点に戻る順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。
次数が奇数の頂点の数が2で、残りの頂点の次数は全て偶数 →ある奇点から出発し、もう一方の奇点へ抜ける順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。