# Tracing the edges of a cube with the minimum pencil lifts.

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?

-

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.