The town of Koenigsberg is crossed by river Pregel which has two islands,
linked by 7 bridges.
Is it possible to walk across all bridges, each exactly once, getting back home ?
Answer is no, as proved by the following theorem.
Let's prove that if a graph has two even vertices, there exist an Eulerian path connecting these points.
And if no odd vertices at all it has an Eulerian circuit.
Suppose this is true for all graphs with less than N vertices and consider a graph with N vertices, having two and only two odd vertices A and B.
Starting from A, at every visited vertex we can leave this vertex, unless it is B and all vertices at B have been used. Then if all edges have been used, we have found an Eulerian path. Otherwise, the part of the graph not visited has at least one less vertex (B), and each connected part has only even vertices. Hence each one has an Eulerian circuit. By merging the visited path with all these circuits, we get an Eulerian path from A to B.
If the graph has no odd vertices, consider two adjacent vertices A and B and delete one edge connecting them. Then the graph has just two odd vertices (A and B) and there is an Eulerian path from A to B. Then an Eulerian circuit through the deleted edge.
And similarily in even much more complicated drawings :
In case it is impossible, this shows how to modify the problem so it becomes possible
(where to add/delete edges for instance).
Here the graph can be drawn in two strikes.
Generally, if a graph has 2n odd vertices, it can be drawn in n strikes.