图的最大匹配个数的下界

The Lower Bound on the Number of Maximum Matchings of a Graph

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.

Let G be a connected graph of order n and let k be the size of maximum matchings in G,where n≥2k+1.In this paper,we present that G contains at least n-2k+1 distinct maximum matchings.In addition,we characterize graphs that possess exactly n-2k+1 distinct maximum matchings.