二部多重グラフにおける最大マッチング数の鋭い下限

概要 我々は、部分と様々な条件の下での二部多重グラフにおける最大マッチングの最小数を研究し、M. Hallによるよく知られた下限を洗練させる。が成り立つ場合、はの各頂点の次数が少なくともであり、はが異なる隣接点を持つとき、最小数はであり、はである。すべての頂点が少なくとも2つの隣接点を持ち、の場合、最小数はであり、ここではである。また、他のいくつかの状況における最大マッチングの最小数も決定する。鋭度の構成の多様性を提供する。