Tight lower bounds on the matching number in a graph with given maximum degree

Let k≥3. We prove the following three bounds for the matching number, α^′(G), of a graph, G, of order n size m and maximum degree at most k. If k is odd, then (Formula presented.). If k is even, then (Formula presented.). If k is even, then (Formula presented.). In this article, we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs. The above three bounds are in fact powerful enough to give a complete description of the set L_k of pairs (γ,β) of real numbers with the following property. There exists a constant K such that 𝛼α^′(G)≥ γn+𝑚βm-k for every connected graph G with maximum degree at most k, where n and m denote the number of vertices and the number of edges, respectively, in G. We show that L_k is a convex set. Further, if k is odd, then L_k is the intersection of two closed half-spaces, and there is exactly one extreme point of L_k, while if k is even, then L_k is the intersection of three closed half-spaces, and there are precisely two extreme points of L_k.