Matching covering maximum-degree vertices in a bipartite graph
ID: matching-covering-maximum-degree-vertices-in-a-bipartite-graph
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.
New to topics? Read the docs here!