# Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices.

We focus on closed walks of length $2L$. Such walks can be described by the sequence of vertices $(u_1,v_1,u_2,v_2,\ldots,u_L,v_L,u_1)$. The $(2k-1)$th edge is given by $\{ u_k,v_k \}$ and the $2k$th edge is given by $\{v_k,u_{k+1}\}$, for $1\leq k\leq L-1$, the last two edges are $\{u_L,v_L\}$, $\{v_L,u_1\}$. The following two properties have to be satisfied:

(P1) $u_k\neq u_{k+1}$ for $1\leq k\leq L-1$ and $u_L\neq u_1$;

(P2) each edge is traversed an even number of times.

The question is: how many closed walks satisfying (P1) and (P2) have $\ell$ distinct edges?

Example: $U = \{1,2,3\}$, $V=\{4,5\}$. The walk $(1,4,2,5,2,4,1)$ does not satisfy (P1) since it comes back to $2$ after $5$, while for instance $(1,4,2,4,1)$ is ok.

I can solve the problem when $N=1$, since in that case (P2) is automatically satisfied (the graph is bipartite but in this very particular case $V$ has only one vertex so...) while I do not know how to start when $N>1$. Do you have some hint?

P.S. I have an algorithm that compute (brute force) the answer given $K$, $N$, $L$. I report here four cases with random choices of $K$, $N$, $L$ for some check, I hope they can be useful: when $K=7$, $N=3$, $L=3$, then $(1134,630)$ are the number of closed walks with $\ell=2,3$ distinct edges; when $K=7$, $N=1$, $L=4$, then $(294,1260,840)$ with $\ell=2,3,4$ distinct edges; when $K=7$, $N=2$, $L=4$, then $(2100,4200,2772)$ with $\ell=2,3,4$ distinct edges; when $K=7$, $N=3$, $L=4$, then $(6930,8820,5796)$ with $\ell=2,3,4$ distinct edges.

Update (combinatorial form): I think that I can rephrase the problem in the following combinatorial form. Let a closed walk be represented by the set of his edges: $$\mathcal{G}=\{ \{u_1,v_1\},\{v_1,u_2\},\{u_2,v_2\},\ldots,\{u_L,v_L\},\{v_L,u_1\} \}.$$ This is a set properly specified by fixing $(u_1,\ldots,u_L)$ and $(v_1,\ldots,v_L)$, where $1 \leq u_k \leq K$ and $1 \leq v_k \leq N$. Elements are actually sets of the form $\{u_i,v_j\}$. Suppose there are $\ell$ distinct elements in this set. For (P2), one has: $$2L = 2n_1 + \cdots + 2n_\ell,$$ where $2n_i$ is the number of times that the $i$th set appears. This number is necessarily even, and $L=n_1+\cdots+n_\ell$. There is a number of ways to obtain this sum and this is given by a standard formula in combinatorics. How many $\mathcal{G}$ satisfying (P1) are there? In other words, how many times $\mathcal{G}$ has $\ell$ distinct elements, each appearing an even number of times, satisfying (P1)?

-
Ok, I updated the question calling more properly them closed walks. I also added a combinatorial form of the problem (I hope this equivalence actually holds) that may help (I hope so). – Monte Carlo Apr 23 '13 at 18:57
Surely {{1,3},{3,1},{1,3},{3,1},{1,3},{3,1},{1,3},{3,1}} doesn't satisfy P1. P1 appears to forbid $\ell=1$. – David Bevan Apr 24 '13 at 8:22
Both your two remark are right! The case $\ell=1$ is not possible. Version improved! :) [sorry I deleted the previous comment, but yes, that graph I wrote down was incorrect] – Monte Carlo Apr 24 '13 at 8:22
In your examples, you seem to be ignoring $E$ completely. Are you also assuming the bipartite graph is complete (i.e. all possible edges between $U$ and $V$ exist)? – Aryabhata Apr 24 '13 at 8:46
@Guido: I've been giving this some further thought and it appears that the numbers from your algorithm may be incorrect. Consider $K=7, N=1, L=4, \ell=2$: Any valid walk has the form $a\,c\,b\,c\,a\,c\,b\,c\,a$ where $a,b\in U$ with $a\neq b$ and $V=\{c\}$. Clearly the possible choices for $a$ and $b$ give a total of $7\times6=42$ such walks, not $294$ as you state. – David Bevan Apr 26 '13 at 15:43

I haven't been able to make any real progress on this (none of my ideas so far have worked out), but here's my own table of numerical results for small values of $K$, $N$, $L$ and $\ell$:
$\quad$
The columns in the inner tables are indexed by values of $\ell$. Where the entry has a "$\cdot$", there are no walks with the corresponding values of the parameters.
The base case can be intuited (verified by your tables) $\ell=2$ gives $K(K-1)N$ paths. – Andrew Szymczak Dec 24 '14 at 9:33
To formalize it a bit, we have $\mathcal{P}(K,N,L,2) = 2{K \choose 2}N$ for L even and $0$ for L odd. With a bit more effort (perhaps I should make a full post), you can get a formula for $\ell=3$. $\mathcal{P}(K,N,L,3) = 2 {K \choose 3} N \left[ 2^{L-1} - (-1)^{L-1} \right] - (K-2) \mathcal{P}(K,N,K,2)$ – Andrew Szymczak Dec 24 '14 at 10:41
Whoops, $\mathcal{P}(K,N,K,2)$ should be $\mathcal{P}(K,N,L,2)$ – Andrew Szymczak Dec 24 '14 at 10:50