An Extension of Moon‐Moser Theorem Involving Bounded Matching Number

The classical Moon‐Moser Theorem gives a tight upper bound on the number of maximal cliques of graphs and characterizations of its extremal construction. In this paper, inspired by a recent work of Alon and Frankl on the Turán problem with bounded matching number, we extend it by giving a tight upper bound on the number of maximal cliques of an ‐vertex graph with matching number at most . Interestingly, the extremal construction depends on the choice of and . We also prove that the number of maximal independent sets of is at most , which is surprising that this value is independent of .