Trace the graph

Put your finger (or mouse) on a dot and drag along the lines. Every line must be drawn exactly once, and you may not lift your finger: lifting ends the attempt. Some of these can be done and some cannot. Before you try each one, press Count odd vertices and make a prediction.

What's going on

Count the lines meeting at each dot. That number is the dot's degree. Whenever your pencil passes through a dot it uses two lines, one in and one out. So a dot with an odd degree can only be where you start or where you finish.

That gives Euler's rule, provided all the dots with lines belong to one connected piece. If every dot has even degree, you can trace the whole thing and end where you began. If exactly two dots are odd, you can trace it, but only by starting at one odd dot and ending at the other. If more than two dots are odd, no route exists, and no amount of cleverness will find one. Separate pieces with lines cannot be traced in one walk; isolated dots do not matter.

The Königsberg bridges have four odd dots. That is the whole reason the townspeople could never find their walk, and the reason Euler invented graph theory to say so.

Sheet: Seven bridges of Königsberg.