How to tell whether a graph can be drawn in one stroke

You may have seen a type of math question that asks you to draw a certain pattern without lifting your pen from the page or going over any line twice. Here is an example. Can you draw this figure without lifting your pen or going over any line twice?

You can get to an answer by trying to literally draw this.

What about the figure below? Can you draw this without lifting your pen or retracing any lines?

Can we use math to solve these questions? Yes, in fact there is a fairly straightforward solution to any of these problems.
Leonard¬†Euler (pronounced “oiler”) , after studying what has become to be known as “The bridges of Konigsberg” problem, realized that by determining whether a vertex (has an even or odd number of lines or paths touching it), one can count up the number of odd vertices for a given figure and then determine whether it can be traced in one stroke… or not. The general rule is as follows:

  • if a figure has > 2 vertices with an odd number of lines/paths leading to them, then the object cannot be drawn in one stroke.
  • If a figure has 2 or less vertices with an odd number, then the object can be drawn in one stroke.

Let’s look at the first object above. How many vertices does it have? I count six. how many vertices have an even number of lines and how many vertices have an odd number? 2 vertices are odd and 4 are even so this object can be traced in one stroke.

Let’s look at the second object above. There are five vertices. 4 of them are odd and 1 is even. As such, this object cannot be traced in a single stroke.

Let’s practice with some more figures. Which of the following, if any, can be traced in a single stroke?

 

Here are some more figures to practice with:

Click to show answers

Answers:

Can be draw in a single stroke:

A, C, E, F, G

 

Cannot be drawn in a single stroke:

B, D, H

Leave a Reply

Your email address will not be published. Required fields are marked *