I know that if n is odd there are no possible walks.
If n is even, I pick 2 random opposite vertices, a and b. From "a" there are only 2 types of "movements" I can do in the graph, clockwise (call it "x") or anti-clockwise (call it "y").
If i want to go from "a" to "b" (random opposite vertices in the graph) in n steps I need to do a permutation of the movements x and y, and i know that the sum of the amount of movements "x" and the movements "y" is n.
Now, if i do an "x" movement and a "y" movement they cancel each other. So assigning the integer 1 to every "x" movement and the integer -1 to every "y" movement, I know that the sum of all the "1"'s and "-1"'s of a set of n movements x and y is going to be equal to either 2 or -2 because the distance between 2 opposite vertices is 2 (in this particular graph).
I'm going to call |x| and |y| to the amount of x's and y's in a set of movements. |x| + |y| = n, and |x|-|y|= 2 or -2.
So I have 2 cases;
a). |x| = (n+2)/2 & |y| = (n-2)/2
b). |y| = (n+2)/2 & |x| = (n-2)/2
I want calculate the amount of permutation of n elements of 2 types "x" and "y".
So I have n!/(|x|! * |y|!). Because case a) and b) are disjoint i can apply the rule of sum and
2*n!/( ((n+2)/2)! * ((n-2)/2)! )
is the number of n sized walks between 2 opposite vertices in a length 4 cycle graph.
Now, in the answer sheet of this problem the solution is 2^(n-1), but i don't seem to understand why. Is there a simple way to understand it?
Thanks!, and sorry if my explanation is kind of confusing.