3
$\begingroup$

I'm 99% sure this isn't possible! But... is there anyway to draw this shape without lifing the pen and without redrawing over any lines?! Thanks :-)

$\endgroup$
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Eulerian_path $\endgroup$ – Harald Hanche-Olsen Jul 10 '14 at 15:21
  • $\begingroup$ Hint: When drawing things like this, if some point has an odd number of lines coming in/out of it, then if you can draw the picture without lifting your pen, you have to either start or end at that point. (Going "through" a point draws two lines, so any point not at the start or end must have an even number of lines meeting it.) $\endgroup$ – Tom Oldfield Jul 10 '14 at 15:23
  • $\begingroup$ Thanks both, based on this the simple answer to my question then is no! $\endgroup$ – Nick Peers Jul 10 '14 at 15:28
6
$\begingroup$

It is not possible.

This picture can be modelled as an undirected graph $G$ in which each vertex represents an intersection and every edge represents a line. Your question then reduces to: does an Eulerian trail exist in $G$?

An Eulerian trail exists iff all vertices have even degree (we start and end in the same vertex) or exactly two vertices have odd degree (we start and end in two different vertices).

Since there are four vertices with odd degree in $G$, the answer is negative.

$\endgroup$
  • $\begingroup$ Look at my amazing disproof: Look at one of the vertices with 3 edges. If you don't start here, then there is a first time you'll enter it through one of the edges. You have to leave thru a second edge. Now, the only way to traverse the third (last) edge is for your drawing to end at this vertex. So, if you don't start at this vertex, then you'll have to end there. The punch line:There are three such vertices :) $\endgroup$ – Behnam Esmayli Jul 19 '16 at 18:57
0
$\begingroup$

Look at my amazing disproof:

Look at one of the vertices with 3 edges. If you don't start here, then there is a first time you'll enter it through one of the edges. You have to leave thru a second edge. Now, the only way to traverse the third (last) edge is for your drawing to end at this vertex.

So, if you don't start at this vertex, then you'll have to end there.

The punch line:There are three such vertices :)

$\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.