3
$\begingroup$

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$ enter image description here

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?

$\endgroup$

4 Answers 4

3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thank you for the answer. but unfortunately, I can't figure out how to continue from your hint. can you please elaborate more on that? $\endgroup$
    – Amirali
    Mar 11, 2021 at 17:04
2
$\begingroup$

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.

enter image description here

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.

enter image description here

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.

enter image description here

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:

enter image description here

[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).

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Wow! thank you very much for the answer and beautiful animation you used. I really appreciate that. $\endgroup$
    – Amirali
    Mar 11, 2021 at 19:15
  • 1
    $\begingroup$ Great answer, except that you don't need an Euler circuit, but merely an Euler path. Which means we can save one line segment. $\endgroup$ Mar 12, 2021 at 1:04
1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Thank you very much. So for the start we connect two of the points with odd degrees and we left with three more segments passing through other odd degree points on other sides of outer big square. so we must pass them twice and the answer is $24+3=27$. am I right? $\endgroup$
    – Amirali
    Mar 11, 2021 at 17:42
  • 1
    $\begingroup$ It must be at least 27. It is probably worth the effort to show that it can be done with 27 segments. $\endgroup$
    – Doug M
    Mar 11, 2021 at 17:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.