WorksMathematics
Clique counts under degree and matching constraints
Abstract
We study the maximum number of -cliques in graphs with maximum degree at most and matching number at most , with no restriction on the number of vertices. For , we determine this maximum whenever and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for , while is uniquely extremal when . We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even . For fixed even and , every extremal graph consists, apart from isolated vertices, of copies of together with a remainder whose order is bounded independently of . When divides , this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.
Introduction
Extremal graph theory studies how large a specified subgraph count can be under certain structural restrictions. For graphs of fixed order, Wang [4] extended the Erdős-Gallai matching theorem to clique counts, while Chao and Dong [2] gave a unified proof of the Gan-Loh-Sudakov conjecture for clique counts under a maximum-degree constraint. Under the simultaneous restrictions of bounded maximum degree and matching number, Chvátal and Hanson [3] determined the maximum number of ’s, that is, edges. Balachandran and Khare [1] subsequently gave a structural proof of the same formula. In this paper, we study the corresponding problem for larger cliques under both constraints, without imposing any restriction on the order of the graph.
All graphs considered are finite and simple. Let and denote the maximum degree and matching number of a graph , respectively, and let be its number of -vertex cliques, counted by their vertex sets. We consider
The endpoints of a maximum matching form a vertex cover of size at most , so . After isolated vertices are deleted, this also gives , and hence the maximum exists. Clearly, for . We use the convention that for whenever or .
The parameters and used by Balachandran and Khare [1] correspond to and . For larger cliques, the edge maximum alone need not identify the extremal graphs.
In Theorems 2.1 and 3.1, we determine for and characterize the extremal graphs. We also give a general upper bound and improve it for even (Theorems 4.1 and 4.3). In the even-degree case, Theorem 4.4 gives a bounded-remainder description of the extremal graphs, from which Corollary 4.5 derives an eventual recurrence.
Let , where denotes the join. If , both and have matching number and maximum degree at most . Put
Clearly, and .
Note that the cases when or are not interesting. This is because a clique of order at least contains matching edges itself, and on the other hand contains vertices of degree . Thus, in either case, .
Tight bound when
As our first result we determine throughout the range , in which the largest clique allowed by the matching constraint is also allowed by the degree constraint.
Theorem 2.1. Let , , and be integers. Then
The only extremal graph is if , and if , up to isolated vertices. If the two values are equal, these two graphs are the only extremal graphs.
Wang [4] proved that the maximum number of ’s in an -vertex graph with matching number at most is
Our formula has the same form with replaced by . But this substitution is not a consequence of Wang’s theorem since a graph of maximum degree may have arbitrarily many vertices.
We first establish two counting lemmas for the proof of Theorem 2.1.
Definition 2.2. For a set , let and denote the numbers of -cliques having at most vertices outside and at least vertices outside , respectively.
Lemma 2.3. Let with , and suppose that and . For every ,
If , equality implies that , every vertex of has degree , and every vertex outside that has a neighbour in is adjacent to all of .
Proof. If , both sides of (3) are zero. Thus we will assume , and for put . Let and be the numbers of -cliques containing zero and one vertex outside , respectively. Counting the cliques containing each vertex of gives
For the second inequality, fix and a neighbour . The other vertices must lie in , giving at most choices. There are at most choices for . Define
Therefore, we get . For , Pascal’s identity gives
Clearly this difference is zero if . Otherwise the difference is
Recall that , and . Therefore, the bracket above evaluates to at least , and therefore the difference is positive. Thus , with equality only at . Therefore,
If equality holds then every , so . Since , equality in the bound for also forces every to have exactly neighbours outside $S. Since is a clique of order , every vertex in has degree . For each outside neighbour of , all possible choices must occur. As $1\leq t-2\leq s-1$, this requires to be adjacent to every vertex of . Therefore the equality conditions follow.
Lemma 2.4. Let , and let be a graph with as its components. Suppose that . Then, for every ,
If , equality holds if and only if , up to isolated vertices.
Proof. We can ignore isolated vertices in . Put for each remaining component, and let . Each component has at most vertices. Now take complete graphs of orders and identify one vertex of each with a single common vertex , keeping all other vertices distinct. The resulting graph has vertices, and every clique of order at least two lies within one of these complete graphs. Therefore
Suppose that and equality holds in (4) and thus in the above chain as well. Since the right-hand side is positive we get . Equality forces to be complete. If there are at least two nontrivial components in , then we will get two vertices in each corresponding to one of these components, which will be non-adjacent, resulting in a contradiction. Hence there is only one nontrivial component of . That component must have vertices, and all its -sets must be cliques, so it is . The converse is easy to check.
Let denote the number of odd components in . The Tutte-Berge formula states that
Let denote the set of all the components of . The Tutte-Berge formula is equivalent to
Let be the odd components of and be the even ones. Let for all . Since and , we have
Proof of Theorem 2.1. Let satisfy , and , and choose to be a Tutte-Berge set for , that is, a set attaining the minimum in (5). Put . Then from (5),
Fix . The cliques with at most one vertex outside are bounded by Lemma 2.3. From (6), . If a clique uses vertices outside , those vertices lie in a single component of and those vertices form a -clique. There are at most choices for its vertices in . Using Lemmas 2.3 and 2.4, (6), and Vandermonde’s identity, we get
Put
We now aim to maximize for integers . For , Pascal’s identity gives
Since , is nonnegative and thus is a convex sequence. Its endpoint values are and , so
For , the second forward difference at satisfies
Thus, the forward differences are nondecreasing and not all equal. Consequently, the average of any proper initial segment of the forward differences is strictly smaller than their overall average. This implies that lies strictly below the line segment joining its endpoint values and at every integer . Hence, the middle inequality in (9) is strict whenever . For , there are no interior integers, so the assertion is vacuously true.
Both endpoint constructions are feasible and attain the corresponding counts in (1), proving (2). Now suppose attains the maximum. (9) and the analysis above imply that or .
If , the bound on the component orders in (6) and equality in Lemma 2.4 imply that apart from isolated vertices. Clearly, this case is possible only when .
If , from (6), every component of has order one, so is a vertex cover. The equality value must be positive, which implies . Thus, we can apply the equality condition from Lemma 2.3. Equality in Lemma 2.3 forces and every vertex of to have degree . Moreover, all vertices outside with a neighbour in have the same neighbourhood . Therefore, there are exactly of these vertices and all the other vertices outside are isolated. Thus apart from isolated vertices. This case is possible only when .
The boundary case
In the previous section, we studied the clique bound when . Here we will study what happens for the boundary case of . It is easy to check that is not interesting, since a clique with order more than contains vertices of degree at least .
Theorem 3.1. For and ,
is the unique extremal graph, up to isolated vertices. For the maximum is zero.
For a vertex in , let denote the set of -cliques meeting . Chao and Dong [2 Lemma 2] proved that for ,
We now establish a lemma as a consequence of the above bound.
Lemma 3.2. Let and . If and , then . Equality holds only for , with possibly one isolated vertex.
Proof. It is easy to check that the result holds when , or when has an isolated vertex. Suppose that and that has no isolated vertex. Suppose for a contradiction that . For a vertex of degree , at most cliques do not intersect with ,
If , convexity of the binomial coefficients gives
Therefore, whenever . If , we instead get . Since we assumed has no isolated vertex, every vertex has degree at least one. Moreover, by the handshaking lemma, not all vertices can have degree . Thus, at least one vertex has degree at most . Therefore, summing these inequalities over contradicts (10). Hence, when and has no isolated vertex.
We now use Lemma 3.2 to obtain the desired bound and extremal graph for .
Proof of Theorem 3.1. Let and let be feasible. We will look into two cases.
Case 1. There exists a vertex such that . Since , we have . Also, . We first show that
Suppose first that . We may apply Theorem 2.1 to with matching bound and degree bound . Writing , we obtain
We claim that the first term is at least the second. For , Vandermonde’s identity gives
where the last strict inequality follows from . For , both terms in the second expression become zero, so the claimed comparison follows. This proves (11) for , and it is easy to check for .
Since , we have . The -cliques in can be partitioned based on whether they contain . The number of -cliques containing is therefore at most . By (11), the number of -cliques not containing is at most . Thus,
Suppose . Therefore, . Since and , this forces and . Thus, . Every vertex of this already has degree , so the degree bound implies that this clique is a connected component of . Moreover, it contains a matching of size , thus it uses up the entire matching budget. Hence no other component can contain an edge. Thus all vertices outside this component are isolated.
Case 2. for every vertex . Gallai’s lemma, in the form used by Balachandran and Khare [1 Theorem 3], says that every nontrivial component is factor-critical and has vertices, where . Let . If there is at most one nontrivial component, then, after removing isolated vertices, has at most vertices. Therefore Lemma 3.2 gives . Equality would require , possibly with one isolated vertex, which is impossible since every nontrivial factor-critical component has odd order.
Now suppose that there are at least two nontrivial components. Let be one such component and , where . By applying Lemma 2.4 to and using convexity, we get
The final strict inequality follows from Pascal’s identity and for . Since the inequality is strict in Case 2, the only extremal graph comes from Case 1, which is with possible isolated vertices.
Conversely, has maximum degree , matching number , and exactly copies of .
Generic upper bound and improvement when D is even
The previous sections determine when . We now give an upper bound valid for all degree and matching bounds, and then improve it when is even. The argument also gives information about the structure of the extremal graphs.
Chvátal and Hanson [3] proved that, for and ,
We first use this result to bound the number of larger cliques.
Theorem 4.1. Let , , and be integers. Every graph with and satisfies
Therefore, .
Proof. Fix an edge . Every -clique containing is obtained by choosing a -clique in . Since , the edge lies in at most copies of . Counting the pairs consisting of a -clique and one of its edges gives
where the last inequality follows from (12). Dividing by proves (13). Since is an integer, the bound for also follows.
Putting in (13) gives exactly (12). For , the bound need not be sharp, since an edge need not lie in all possible copies of . We will now keep track of some of this loss.
For and , put
Note that throughout this range.
Lemma 4.2. Let , where , and let . Obtain from by deleting all components isomorphic to and all isolated vertices. Then
Proof. Call an edge deficient if , and let be the set of all deficient edges. Every edge lies in at most copies of , whereas a deficient edge lies in at most
such copies. Therefore, counting the number of -cliques containing each edge gives
We claim that every vertex of is incident with a deficient edge. Let . If , then every edge incident with is deficient. Suppose instead that and no edge incident with is deficient. For each , this gives , so is adjacent to every vertex of . Thus . Every vertex of this clique already has degree , so it is a component of . This contradicts the choice of .
Since has no isolated vertices, the claim gives . Substituting this into the preceding inequality proves (15). □
Notice that Lemma 4.2 does not require to be even. Let , write , where , and put . Define and
These two expressions are the clique counts of the complete and complete split constructions introduced earlier, respectively. We write for the disjoint union of copies of .
Theorem 4.3. Let , , and be integers. Write , where . Then
Proof. For , let be whichever of and has more -cliques, and let be the empty graph. Since , we have and . Thus is feasible and has copies of , proving the lower bound.
For the upper bound, let be feasible. We may assume that , otherwise, add disjoint copies of . Since and , this does not change or violate the degree bound. Let be the number of components of isomorphic to , and obtain by deleting these components and all isolated vertices. Each deleted -component has matching number , so and . Therefore, . Also, (12) gives
Since , Lemma 4.2 gives
Dividing by and using integrality proves the upper bound.
For the same parameters as above, Theorem 4.1 gives
Thus (17) subtracts from the remainder term before rounding. This is a strict improvement of the unrounded estimate when , although the rounded bounds can coincide. When , both bounds are attained by .
We now use the same argument to describe every extremal graph when is even.
Theorem 4.4. Let , , and be integers, and put . Every graph attaining , after its isolated vertices are deleted, has the form
where has no -component and is extremal for . Moreover,
Therefore, if , then
and is the unique extremal graph, up to isolated vertices.
Proof. Write , where , and let be extremal. Delete all its components isomorphic to and all isolated vertices to obtain . Since , every copy of must be a connected component of , as each of its vertices already has neighbours within the clique and hence cannot have any neighbour outside it. Thus, , up to isolated vertices, and has no -component. By Theorem 4.3, . Combining Lemma 4.2 with (18) gives
This proves . Since , the graph is feasible for . If it were not extremal for this remaining matching bound, replacing it by a better feasible graph would increase without violating either constraint. Thus is extremal for . It remains to bound . The inequality gives . To obtain the upper bound even when , add disjoint copies of to , and denote the resulting graph by . This graph is still feasible and extremal, has matching number , and has the same components isomorphic to . Its remainder therefore has matching number . Applying the order bound already proved in (22) to gives
Hence , proving (20).
Finally, if , then . Thus is empty and , so . The graph attains (21), proving the uniqueness assertion.
Corollary 4.5. Let , , and be integers, and put . If , then
Moreover, up to isolated vertices, the extremal graphs for are exactly the graphs
where is extremal for .
Consequently, for fixed and , determining and its extremal graphs for all reduces to determining them for finitely many values of .
Proof. Let be extremal for , and let be its number of components isomorphic to . By Theorem 4.4,
Therefore , so contains a -component. Delete one such component to obtain . Since and matching number is additive over components, we have
Thus is feasible for , giving
Conversely, adjoining a disjoint copy of to any extremal graph for gives a graph with maximum degree at most , matching number at most , and exactly copies of . This proves (23) and shows that every graph constructed in this way is extremal.
For the graph obtained by deleting a -component from an extremal graph , the recurrence gives
Hence must itself be extremal, proving the claimed characterization.
Finally, for fixed and , the threshold depends only on the remainder . Subtracting preserves this remainder. Therefore, we may apply the recurrence and the extremal characterization repeatedly until the remaining matching bound is at most this threshold or is less than . Since has only finitely many possible values, only finitely many matching bounds remain to be considered.
References
- [1]Niranjan Balachandran and Niraj Khare. Graphs with restricted valency and matching number. Discrete Mathematics, 309(12):4176–4180, 2009.DOI
- [2]Ting-Wei Chao and Zichao Dong. A simple proof of the Gan-Loh-Sudakov conjecture. The Electronic Journal of Combinatorics, 29(3):P3.59, 2022.DOI
- [3]Vašek Chvátal and Denis Hanson. Degrees and matchings. Journal of Combinatorial Theory, Series B, 20(2):128–138, 1976.DOI
- [4]Jian Wang. The shifting method and generalized Turán number of matchings. European Journal of Combinatorics, 85:103057, 2020.DOI