How many n sized walks exist between 2 opposite vertices in a C4 (length 4 cycle graph)?

Question

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.

Answer 1

There are $2^n$ walks of length $n$. If $n$ is even, then these walks come in two types: closed walks that start and end at the same vertex, and walks that start at one vertex and end at the opposite vertex.

The number of walks of each type is the same. If we take a closed walk and reverse the direction of the last step, then instead of ending up at the start, we end up at the vertex opposite the start. Similarly, if we take a walk of the second type and reverse the direction of the last step, we end up with a closed walk.

So the number of walks of each type is $2^{n-1}$.

The flaw in your approach is that the difference $|x|-|y|$ does not have to be $2$ or $-2$. If it is $6$, for instance, then we end up with a closed walk that loops around the $C_4$. In general, $|x|-|y|$ must be an even integer not divisible by $4$, if we want to end up at the opposite vertex.

Answer 2

You are counting walks from a vertex $a$ to the opposite vertex $b$. Call the other two vertices $c$ and $d$. If $n$ is even and $n\gt0$, then any walk of length $n-1$ starting from $a$ will leave you on $c$ or $d$, one step away from $b$. Therefore, the number of walks of length $n$ from $a$ to $b$ is equal to the number of walks of length $n-1$ from $a$, which is $2^{n-1}$ since each vertex has degree $2$.

Of course, if $n$ is odd or $n=0$, there is no walk of length $n$ from $a$ to $b$.

Answer 3

This can be handled readily through ad hoc methods like in the other answers---both of them efficient---but this problem can be treated using a more general method that works more or less as well to answer analogous questions for more complicated graphs.

For a finite graph $\Gamma$ with vertices $v_1, \ldots, v_n$, define the adjacency matrix $A$ of $\Gamma$ to be the matrix whose $(i, j)$ entry is the number of edges connecting $v_i, v_j$. Then, an inductive argument shows that the number of paths from $v_a$ to $v_b$ of length exactly $n$ is the $(a, b)$ entry of $A^n$.

To compute powers of $A$, as usual we put $A$ in Jordan normal form $P J P^{-1}$ (since $A$ is symmetric by definition, it is diagonalizable). Then, $A^n = (PJP^{-1})^n = PJ^n P^{-1}$.

In our case, labeling the edges in order gives the adjacent matrix $$A = \pmatrix{0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0} ,$$ and the Jordan decomposition is given by $$J := \operatorname{diag}(2, -2, 0, 0), \qquad P := \pmatrix{1&1&1&0\\1&-1&0&1\\1&1&-1&0\\1&-1&0&-1} .$$ Now, $J^n = \operatorname{diag}(2^n, (-1)^n \cdot 2^n, 0, 0)$, so to write an explicit formula it is convenient for $A$ it is convenient to split cases according to the parity of $n$. For $n > 0$ even, $$A^n = 2^{n - 1} \pmatrix{1&0&1&0\\0&1&0&1\\1&0&1&0\\0&1&0&1} .$$ In particular, the number of paths of even length $n$ connecting the opposite vertices, say, $v_1, v_3$, is $$\color{#df0000}{\textrm{$n > 0$ even:}\qquad\boxed{(A^n)_{13} = 2^{n - 1}}} .$$ Similarly, for odd $n$, $A^n = A^{n - 1} A = 2^{n - 1} A$, but $A_{13} = 0$, so the number of paths is $$\color{#df0000}{\textrm{$n$ odd:}\qquad\boxed{(A^n)_{13} = 0}} .$$