Hola, la idea es más o menos así: elegí un vértice y su opuesto, observa que los caminos de largo impar, no te llevan a ninguno de esos vértices, te dejan en los otros. Así que con n impar siempre estas en alguno de los otros dos vértices, y desde ellos, podes llegar a tu vértice "destino". Observa también que en cada nodo podes moverte hacia otros dos nodos. Por lo tanto siempre tenes 2 opciones, por lo que en n-1 pasos vas a donde quieras (2^(n-1)), y en un paso más vas al destino. La solución es entonces 2^(n-1)*1.
Saludos!