29 of 100: Trace It!

There are only two junctures which have an odd number of paths going to them. One needs to be the start, the other the end of the line. The details of the path through the other junctures may be different between solutions.

One possible solution is below. Start by drawing the black path back to starting point, then follow the red path to the end.

The above problem is related to the Eulerian circuit problem in graph theory, that is traversal of a graph without breaks and starting and ending at the same vertex and the related Eulerian Path problem (the problem above is related to the latter) where one can begin and end at different vertices. The former is possible only when all vertices are of even degree and the latter is possible if either 0 or 2 vertices have odd degree. Our diagram above can be simplified to a 5 vertex graph, 3 of degree 4 (where the lines intersect) and 2 of degree 3 where the lines touch the encircling quadrilateral). Since there are 2 and only 2 vertices of odd degree, the figure can be traced completely with the given conditions.

I used different colors in the figure only to make it easier to visualize.

Although I am not sure if it is commonly known around the world, I was familiar with a very similar puzzle, only with a different figure to trace. Fortunately, It did not take long to realize that the figure above was actually a deformed version of the one I knew "the house with X".

I think it was my aunt who introduced me to the puzzle, many years ago (perhaps a decade, maybe more). I did not expect it to become useful after all these years, but I had found a few different solutions, all of which work for this one as well. Below is an example:

This is probably not a very 'mathematical' approach compared to many of the other solutions given, but I think it comes down to the same thing. I was unknowingly familiar with an example of a Euler Path problem, which was essentially identical to the one above.

Here is a possible solution.

The solution is what's called an Euler Path. If you look at the number of edges that meet at each vertex, you'll notice all vertices but two are the junction of an even number of edges. When there are exactly two vertices with an odd number of edges this means every line can be drawn exactly once, but the path will start and end at different vertices (if all vertices had an even number of edges that's an Euler Circuit- where the path will start and end at the same point); the two odd vertices will be the starting and ending points, and there are multiple paths between those two points.

Yes, applying Euler's Theorem, a basic result from graph theory. This theorem states that a path over the entire (connected) graph using each edge exactly once,exists when there are two or less vertices of odd order. When all are even the path can start and end at the same vertex, when there are two odd vertices the path must start at one and end at the other.

The example given is a graph with two vertices with odd order and the rest have even order. By Euler's theorem there exists a path, using each edge exactly once, over the entire graph starting at one odd vertex and ending at the other.

That is an Eulerian graph.

Follow the rainbow. It's pretty self-explanatory!

Just trace

Just look for two intersections that is connected by odd-numbered lines. There must be at most 2 of these. Otherwise, it couldn't be traced entirely.

It is not possible starting from any point. It is possible starting from either one of two points.

*This solution was in response to the previous wording of the question. I don't remember the exact wording, but it was something like:

Starting with your pencil at any point on the two-dimensional figure, is it possible to trace this entire figure without lifting your pencil or redrawing a line? (Crossing at an intersection is ok.)

But since this is clearly a geometry problem and not a logic problem, maybe I shouldn't have been so persnickety.

Brilliant Logo