Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
1  
This is nice - I don't have to keep looking for a solution. My wife is making crochet cubes, and starting a run is a little harder than continuing one. –  Chris Dec 7 '12 at 19:28
    
@Chris: Now that’s an unusual context for a little applied graph theory! –  Brian M. Scott Dec 7 '12 at 19:31

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.