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:
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.
What you are asking for is how to find an "Eulerian path"
This page explains it quite well:
https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf
Also, there's this page:
http://www.ctl.ua.edu/math103/euler/howcanwe.htm
Which, says, to paraphrase:
If there's 0 odd vertexes then there's at least an Eulerian circuit, an Eulerian path that ends where it begins, if there's 2 odd vertexes there's at least an Eulerian path. Anything else has no paths or circuits.
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. --Mike Earnest
And such a path would look like :
Answer:
This is impossible. The question asks for the existence of a Eulerian path. For this to work, exactly zero or two vertices must have an odd degree, but here, the four corners of the squares have an odd degree. Also related to Seven Bridges of Königsberg problem.
