Can you determine if it's possible to draw a geometric figure (made up from shapes like rectangles, triangles, and other regular shapes) with one pen stroke and not drawing the same line twice.
I am thinking about something related to graph theory or something like that.
For example, something like this:
Answer
Yes! This is a classic graph theory problem. Anywhere where lines meet is called a vertex, and the degree of a vertex is the number of lines that meet there. Euler proved that as long as a graph has either 0 or 2 vertices of odd degree, and the graph is connected (consists of a single piece), then it can be drawn as you specified. Furthermore, if there are any odd vertices, then any successful Eulerian path (as such a pen stroke is called) must start at one, and end at the other.
The main reason this is true is as follows: every time you enter and leave a vertex, you kill two of its edges. So, if a vertex has an odd number of edges, not all of its edges can be taken care of by passing through it, so the pen must start or end there. There are only two start and end points, so there can be at most two odd degree vertices.
In your picture, there is a square with horizontal sides, all of whose vertices have 5 edges coming out of them. This means that you have $4$ odd-degree vertices, which is $2$ too many, so your graph can't be drawn with a single non-overlapping pen stroke. But, if you erased one of the diagonals of this middle square, then you'd be in business.
This result applies to any shape with various curves on a page which meet at various places, not just straight line figures.
No comments:
Post a Comment