##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 194.25401

**Autor: ** Elliott, P.D.; Erdös, Pál

**Title: ** Some matching theorems (In English)

**Source: ** J. Indian Math. Soc., n. Ser. 32, 215-219 (1968).

**Review: ** The authors give the following improvements of an earlier result of the first author [Mathematika, London 13, 23-25 (1966; Zbl 144.00504)].

Theorem 1. Let G be an even (i.e. bipartite) graph of type (n,n) and suppose that G has at least (½+c)n^{2} edges, and has at least one matching. Then G has at least (1) 2^{\mu}\mu! distinct matchings, where (2) \mu = [1/2m], m \geq \alpha n, \alpha = 1-(1-2c)^{ ½}, and m is an integer. In particular, if c is fixed and n large, the number of distinct matchings exceeds (n!)^{c1} where c_{1} > 0 depends only upon c.

Theorem 2. Let G satisfy the hypotheses of Theorem 1 with 2c > \sqrt 3-1. Then G has at least m! distinct matchings where m is an integer satisfying m+1 \geq n(2c-(2-4c)^{ ½}).

**Reviewer: ** R.L.Hemminger

**Classif.: ** * 05C70 Factorization, etc.

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag