Example: The “House of Nikolaus”

Deciding whether a graph can be drawn in one line and passing each edge only once is rather easy. One only needs to calculate the rank of each vertex and look whether there are at most two vertices with an odd rank.

Here we are going to determine all possible paths to draw such a figure. As an example we take the popular “House of Nikolaus”. This idea and an implementation can be found in the book of Michael Trott: “Mathematica Guidebook Programming”.

Preliminary remarks:

all the possible lines have to start at position A or E, since these are the vertices with an odd degree

The solution is going to be obtained in form of a list: {so far drawn line segements, not drawn line segments}

The line to be drawn next has to begin at the endpoint of the line segments drawn so far.

The lines are to be represented in form of (unoriented) pairs {start,end}.

So we get the line strokes of the house as the following pairs:

Using the pattern {u___,y_,v___} we can use unoriented lines segments in the lists of the drawn and not yet drawn parts (this is really tricky an a good example of pattern matching!)

Now a rule to ad a line to an already drawn segment:

The tricky part here is, that in the triple {y,u,v} , one of the variables u,v is empty, due to the pattern {u___,y_,v___} and the segments not jet drawn are represented in the form: {α,Line,γ}:

Let us look at the following start configuration, i.e. we start with the line {a,d}

Applying the rule at the start configuration we get:

To get all possibilities for the second stroke we use the command ReplaceList, this yields:

We get all the possibilities when repeating this process until all segments are drawn, i.e. we have to repeat seven times (we have eight edges and one drawn as our starting segment., so seven segments remain.

Flattening the result gives a list of possible strokes:

So this are 16 solutions:

Next we calculate all possibilities for the start configuration {a,b}:

For the last start configuration we get again 16 possible solutions:

Making the union of all the intermediate results (to eliminate duplicates) we get 44 (different) solutions

To make the sequence of the strokes more visible we can define the colors in one special order, to be used for every house to be drawn:

Then we make a slight modification to the drawing function to implement the sequence of colors:

Then: