= Matching covering maximum-degree vertices in a bipartite graph
A finite <bipartite graph> of positive <maximum degree> $\Delta$ has a <matching in a graph> covering every <vertex> of <vertex degree> $\Delta$. To cover the <vertices> of <maximum degree> in one side $A$, apply <Hall's marriage theorem> to that <subset>: for each <subset> $S$ of it, <double counting> gives $\Delta|S|\leq\Delta|N(S)|$, where $N(S)$ 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.
Back to article page
