# Can this shape be traced in a single line without lifting my pencil of the paper?

Recently, a friend of mine gave me this challenge to trace this object in one line, without lifting a finger of the paper, and without tracing a line more than once, saying it was possible.

P.S, the curvy squares at the end are actually ment to be semi-circles

Every time I try to do it myself, I always get so close with only one line left. I know this type of problems is generally solved using graph-theory (Not saying that this is necessarily solvable) , so any help is appreciated!

-
Perhaps you accidentally the shape. – T. Bongers Jan 8 at 20:43
@user: Did you intentionally the verb? – Brian Tung Jan 8 at 20:44
@BrianTung As a general principle, I never intentionally. – T. Bongers Jan 8 at 20:45
Ladies and gentlemen, I present to you, the null euphemism. – Brian Tung Jan 8 at 20:46
Your friend just wanted to keep you busy for a while. It's not possible. – Daniel Fischer Jan 8 at 20:47

Not possible, by Euler: There are four vertices of odd-degree. In the best case, you will be missing a line connecting two of the corners.

-
This is correct, for further reading, consult en.wikipedia.org/wiki/Eulerian_path – Gabriel Islambouli Jan 8 at 20:47
Even if the curved-ish squares on the outside of the box are semi-circles? – Michael Jan 8 at 20:49
@Michael, in general, the geometric positioning of a graph has no impact on its structure. – Bob1123 Jan 8 at 20:51
So what is this talk of vertices (I am a layman in graph theory). Can you briefly explain what they are? – Michael Jan 8 at 20:53
Vertices, roughly speaking, are points where one or more lines (edges, in graph parlance) terminate or meet. They're also sometimes called nodes, though that is somewhat more common in computer science, which frequently uses graph theory. The degree of a vertex is the number of edges that meet at that vertex. One of Euler's theorems indicates that the kind of path you want (never retraces, never lifts pencil) can be drawn if there are either exactly zero or exactly two vertices of odd degree. (The number of vertices of odd degree must be even.) If it's zero, the path is a circuit. – Brian Tung Jan 8 at 20:58

What you're wondering is if there is something called a Eulerian Path in this graph. An Eulerian Path is a sequence of edges in the graph, with consecutive edges incident in the graph, and this sequence of edges contains each edge of the graph exactly once. You can prove that a graph has an Eulerian path if it is connected and has at most two vertices of odd degree. If all the vertices are of even degree, then there actually exists an Eulerian circuit, a path that ends where it starts.

-
One must state that either exactly two or zero vertices have odd degree; if only one vertex has odd degree, there is no Eulerian Path. – Milo Brandt Jan 8 at 20:54
@MiloBrandt, there is no graph with only one vertex of odd degree. The sum of the degrees in a graph is exactly twice the number of edges, an even number. If there were only one vertex of odd degree, this sum would be odd, a contradiction. Thus all graphs have an even number of vertices of odd degree. – Bob1123 Jan 8 at 20:57
Ah! I understand. Thank you. I guess I've seen the result stated with "exactly zero or two vertices of odd degree" and didn't think about it hard enough. – Milo Brandt Jan 8 at 21:01
No problem. The sum-of-degrees trick is a handy one. – Bob1123 Jan 8 at 21:03

It is possible, to trace any figure, by tracing back along the same line again! If you add the condition that you can go along a side only once, then it is not possible. At each vertex, you must (i) begin tracing, (ii) end tracing, or (iii) pass through. If you pass through you must enter along one line and exit along another, you use two edges. If a vertex has an odd number of lines emanating from it, the path must either start or end at that vertex. This figure has all four vertices with an odd number (5) of lines. But you must say "using each side only once". Without that any figure can be drawn.

-

The proof of whether it is or is not possible is in the line junctions. There can be only two junctions with an odd number of lines forming the junctions. The trace will start at one odd-line junction and end at the other.

-