A finite bipartite graph of positive maximum degree has a matching in a graph covering every vertex of vertex degree . To cover the vertices of maximum degree in one side , apply Hall's marriage theorem to that subset: for each subset of it, double counting gives , where is its graph neighbourhood. Construct the corresponding matching in a graph for the other side, then use the union of two matchings to cover both specified subsets simultaneously.
Articles by others on the same topic
There are currently no matching articles.