Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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: \begin{equation}\mathcal{G}=\{ \{u_1,v_1\},\{v_1,u_2\},\{u_2,v_2\},\ldots,\{u_L,v_L\},\{v_L,u_1\} \}.\end{equation} 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: \begin{equation} 2L = 2n_1 + \cdots + 2n_\ell,\end{equation} 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)?

share|cite|improve this question
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$ table of values

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.