Select a vertex $V$ of a cube. How many paths begin at $V$, traverse exactly $3$ edges of the cube, and end at the vertex furthest from $V$?
Number of paths that begin at vertex, traverse $3$ edges of cube and end furthest
1
$\begingroup$
graph-theory
-
0What have you tried? If you just try listing them, do you run into any problems? – 2012-12-18
1 Answers
2
Hint: Draw a cube, making sure to include the "invisible" edges. Now take advantage of symmetry. The first step is to any one of $3$ vertices. Pick one of these vertices, say $W$, and count the number of paths of length $2$ that get you where you want to go. Then multiply your count by $3$.