Drawing the grid without lifting the pen

Question

The below shape consist of $24$ segments with unit length. if we want to draw this shape without lifting the pen, what is the minimum length of the line we should draw? $1)25\quad\quad\quad\quad\quad\quad2)26\quad\quad\quad\quad\quad\quad3)27\quad\quad\quad\quad\quad\quad4)28\quad\quad\quad\quad\quad\quad5)29\quad\quad\quad\quad\quad\quad$

I think we can do it somehow by segments with the length $28$ (by passing twice the four middle segments on each side of outer big square).

I'm not sure how to solve this problem. is it possible to solve it mathematically or I should just try different ways to draw this?

Answer 1

The figure has 4 nodes with 2 lines connected to node. 8 nodes with 3 lines connected, and 4 nodes with 4 lines connected.

If you want to complete the circuit without lifting your pen, you can start at a node with an odd number of connections, and you can end at a node with an odd number of connections, for all the rest you must have an even number of connections. That is, if you get to the node on one path you leave the node on a different path.

This means that you must double up on some of the lines where it appears that there is a odd number of lines to make it an even number. What is the minimum number of lines you need to double up such that there are at most two nodes with an odd number of connections?

Answer 2

Notice that if you draw it without lifting the pen, except for the starting and ending point you must draw the same number of lines going into each point as going out. This means that you must draw an even number of segments meeting every point except possibly two. How many extra segments does this imply you need at a minimum? Can you achieve this?

Answer 3

Every node must have the same number of edges entering and leaving, except for the end points. There are 8 nodes on the graph with an odd degree, but we can make two of them the endpoints, so we have 6 nodes that need an "extra" edge. Finally, we can note that the odd-degree nodes come in adjacent pairs, so the "extra" edge leaving one node can be the "extra" edge entering another, so we only need half as many "extra" edges as we have non-endpoint, odd-degree nodes.

Answer 4

You will be able to draw all the edges of the graph without lifting the pen and drawing every edge exactly once (starting and ending at the same node), iff there exists an Euler circuit in the graph.

We shall use the following theorem: a connected graph has an Euler circuit iff all the nodes of the graph has even degree.

The given grid graph does not have all nodes with even degree. Let's first find the nodes with odd degrees, as shown in the next figure. Notice that the nodes B,C, E,I, H,L and N,O have odd degrees (namely 3).

Let's add 4 additional (red) edges to the grid graph as shown in the next figure to make all the nodes have even degrees.

Now, in the augmented graph above, by the theorem, it must have an Euler circuit, so we shall be able to draw all the edges of the graph exactly once without lifting the pen.

We shall use Flury's algorithm to find an Euler circuit in the augmented graph first. The key idea is that when you have a choice between a bridge and a non-bridge, always choose the non-bridge (don't burn the bridges).

Since the augmented graph has all nodes with even degrees, we can start at any node, let's start at B, a node with degree 4 in the augmented graph.

Using the algorithm, the following animation shows how to construct an Euler circuit in the augmented graph.

Now, let's find where the additional edges (ones not present in the original graph) were used in the circuit found in the augmented graph.

Let's go back to our original graph by replacing those edges by the ones in the original graph, we had exactly 4 such additional edges needed to make all nodes in the original graph to have even degrees.

It implies that in order to have the Euler circuit in the original graph we need 4 additional edges (requiring 24+4=28 edges). It also means that in the original graph we need to traverse the corresponding 4 edges twice, in order to draw all the edges without lifting the pen, as shown below:

[EDIT]

If we don't need to start and end at the same node, it's sufficient to have an Euler trail instead of a circuit, needing one less edge: $28-1=27$ edges (only 3 edge segments, namely, EI, ON and HL are needed to be traversed twice, leading to minimum length of the line as $24+3=27$).

In this case the trail shown above starts at $B$ but ends at $C$ (instead of $B$ as before), since the edge $BC$ has already been visited once, we don't need to visit it again (as shown in the next figure).