一筆書き

一筆書きとは、ペンを紙から一度も離さずに図形を描くことである。例えば、三角形や四角形は一筆書き可能だが、十字「+」は一筆書きできない。

与えられた図形が一筆書き可能かどうかという問題の例として、「ケーニヒスベルクの問題」が知られている。

ケーニヒスベルクの問題

ケーニヒスベルク（旧ソ連）に、以下のように7つの橋が架かっている場所がある。

この7つの橋を各1度ずつ通って、元の場所に戻ってくることができるかどうか? ただし、同じ橋を2度以上通ってはならない。

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

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

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

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