3
$\begingroup$

I have an ordinary cube with the standard 8 vertices and 12 edges. Say I define a path as a journey along the edges from one vertex to another such that no edge is used twice. Then I pick two vertices that are connected by a single edge, ie. a path of length 1. How would I go about proving that all the paths between these two points are always odd in length, ie. each such path consists of an odd number of edges.

Ideally I'm after an explanation that could be understood by a high school student. Which is another way of saying I'm trying to help my daughter with her maths homework :)

$\endgroup$
4
$\begingroup$

Imagine to color the vertices of the cube in this way:

enter image description here

Now imagine you start from a red vertex. Doing one step, in any direction, you go in a blue vertex. It is easy to verify that this hold for each red vertex.

Now check the blue vertices. It is easy to see that from one blue vertex, with one step, you can only go to a red one.

So, if you start from a red vertex, at each odd step you will be at a blue vertex, and at each even step you will be again at a red vertex. This works no matter long is the path, and it can even go back and forth.

So, since two adjacent vertices have different colors, only odd-length paths can join them.

$\endgroup$
  • $\begingroup$ Nice thought! +1 $\endgroup$ – Max Payne Feb 23 '16 at 14:42
  • $\begingroup$ Nice answer, thanks. $\endgroup$ – dave Feb 23 '16 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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