On the Number of Group-Weighted Matchings

Let G be a bipartite graph with a bicoloration {A,B}, |A|=|B|. Let E(G) A x B denote the edge set of G, and let m(G) denote the number of perfect matchings of G. Let K be a (multiplicative) finite abelsian group |K| = k, and let w:E(G) K be a weight assignment on the edges of G. FOr S E(G) let w(S) = _eSw(e). A perfect matching M of G is a w-matching if w(M)=1. We shall be interested in m(G,w), the number of w-matchings of G.It is shown that if deg(a) d for all a A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.