Drawing a House

October 17, 2021

During a night of drink­ing at a friend’s, a ques­tion ran­dom­ly came up:

Given the shape of a simple house with a cross inside of it, can you draw it with a pen with­out lift­ing it up?

house 1

It can be fig­ured out quite easily with a bit of time, but what’s the fun in that? Know­ing a little bit of graph theory can go a long way in prov­ing not only that a solu­tion does indeed exist, but that all solu­tions have to start (and end) a par­tic­u­lar way — from bottom of the house up.

To under­stand how graph theory can help, we first have to under­stand two things: the degree of a node in a graph, and Euler paths.

The degree of a node

The degree of a node in a graph is how many edges are con­nect­ed to it. If we anno­tate the house with the degree of each node, this is what it looks like:

house 2

Euler path

An Euler path is a path taken through a graph that uses each of its edges exact­ly once. Notice how it maps almost per­fect­ly to our prob­lem?

Fur­ther­more, we know a bit more about the exis­tence of Euler paths in graphs. First­ly, not all graphs have Euler paths — only graphs with a par­tic­u­lar char­ac­ter­is­tic have them. This char­ac­ter­is­tic is:

A graph that has an Euler path has at most two nodes with an odd degree.

The corol­lar­ies to this rule are:

  • Aside from the above nodes with an odd degree, all other nodes must have an even degree.
  • The number of nodes with an odd degree is either zero or two (since the sum of the degrees of all nodes in a graph is always even).

Why does this rule work? If we look at a few degen­er­ate exam­ples, it becomes clear why it makes sense intu­itive­ly.

See the fol­low­ing graph:

house 3

You can see that the two nodes with an odd degree will be the start and end of the path. All other nodes with an even degree rep­re­sent the fact that the path will enter and exit the node equal­ly often, and there won’t be a case where a path is “stuck”.

If there are no nodes with an odd degree, the path can start and end at any node. This is also known as an Euler cir­cuit.

house 4

Check out this graph with one node of degree four and four nodes of degree one. It does­n’t have an Euler path.

house 5

How­ev­er, if we add an edge like this, it sud­den­ly becomes pos­si­ble:

house 6

With these two con­cepts in mind, it becomes clear that an Euler path does exist in this house graph, as seen in the anno­tat­ed graph above, shown again below:

house 2

Since the bottom two nodes are the two nodes with an odd degree, a pen trying to draw such a house must start and end at either of these two nodes, for exam­ple:

house 7

As an adden­dum, Euler paths should not be con­fused with Hamil­ton­ian paths. A Hamil­ton­ian path is a path taken through a graph that uses each of its nodes exact­ly once, instead of each edge. Find­ing the exis­tence of an Hamil­ton­ian path is much less triv­ial; in fact, it’s NP-com­plete.