3
$\begingroup$

I have a cube. I want to trace all the edges of the cube only once, lifting my pencil as few times as possible.

Look at the top of a cube, and label the top left vertex as a and travel Clockwise labeling b, c, and d, with point e under a, f under b, g under c and h under d.

The best I've been able to do is trace a-b,b-c,c-d,d-a,a-e,e-f,f-g,g-h,h-e. Then I have to clean up with b-f, then c-g, then d-h. This gives me 4 pencil traces.

Is there a way to do it with fewer traces?

2 Answers 2

2

There is not. You’re trying to trace the $12$ edges of a graph with $8$ vertices, each of degree $3$. When you go into a vertex and then out of it, you use up $2$ of the $3$ edges at that vertex; the remaining one then has to be at one end of a trace. Thus, each vertex must be an end of some trace, and since a trace has at most two ends, you need at least four traces to accommodate all eight vertices. You’ve shown that four traces also suffice.

For more information, you might want to read about Euler paths.

  • 0
    @Chris: Now that’s an unusual context for a little applied graph theory!2012-12-07
1

In every odd-degree vertex one path has to start/end. Since there are 8 vertices of degree 3 you have to use 4 paths.