Generalization of Erdős–Gallai edge bound

Erdős and Gallai proved that a simple graph GG with nn vertices and matching size νν has at most max{2ν+12,ν2+(n−ν)ν} edges. The bound is tight for all positive integers nn and νν. We obtain the previous Erdős–Gallai bound as a corollary of our result. The result provides a precise bound for the maximum number of edges possible in a simple graph with restricted values of maximum matching size and independence number. This article further provides sharp bounds for the maximum number of edges possible in a simple graph with restricted values of number of vertices, maximum matching size and independence number. We also establish uniqueness of these extremal graphs that achieve the edge bound subject to conditions on nn, νν and αα- the independence number. In case, the extremal graphs are not unique for the given values of nn, νν and αα, we provide the whole class of the extremal graphs that achieve the edge bound.