pith. sign in

arxiv: 2606.09733 · v1 · pith:OUWLGZSHnew · submitted 2026-06-08 · 🧮 math.CO

On saturation problems involving clique number and matching number

Zian Chen , Guorong Gao , Jianfeng Hou , Yue Ma This is my paper

Pith reviewed 2026-06-27 15:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords K_r-saturated graphsmatching numberextremal graph theorysaturation problemsedge minimization
0
0 comments X

The pith

For large n, any n-vertex K_r-saturated graph with matching number s has at least (r-1)n minus a constant edges, with equality graphs identified.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the smallest possible number of edges in an n-vertex graph that contains no K_r yet becomes non-K_r-free upon addition of any missing edge, while also having matching number exactly s. It gives two explicit lower bounds, one when s equals r-1 and one when s exceeds r-1, each linear in n with an additive term depending only on r and s. The work completely describes the graphs that attain these minima once n is large enough. A reader would care because the matching-number constraint refines the classical minimum-edge result for K_r-saturated graphs and shows how an additional global parameter alters the extremal structure.

Core claim

If G is an n-vertex K_r-saturated graph with ν(G)=s and n is sufficiently large, then e(G) ≥ (r-1)n - r(r-1)/2 -1 when s=r-1, and e(G) ≥ (r-1)n + (s-r)^2 - (r+2)(r-3)/2 -5 when s>r-1, with the equality graphs completely characterized in each case.

What carries the argument

K_r-saturation together with a fixed matching number s, which partitions the problem into the cases s=r-1 and s>r-1 and forces the extremal graphs to be specific near-complete multipartite constructions.

If this is right

  • When s equals r-1 the minimum edge count is exactly (r-1)n minus r(r-1)/2 minus 1.
  • When s exceeds r-1 the minimum edge count is exactly (r-1)n plus (s-r) squared minus a fixed term in r.
  • All graphs achieving the minimum are identified for large n.
  • The classical saturation bound without a matching constraint is recovered in the limit as s grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar lower bounds may exist when saturation is paired with other global parameters such as chromatic number or independence number.
  • The threshold for 'sufficiently large n' could be made explicit by tracking the constants hidden in the proof.
  • The equality graphs for the two cases on s may admit a unified description that interpolates between them.

Load-bearing premise

The bounds and characterizations are asserted only when the number of vertices n is sufficiently large compared with r and s.

What would settle it

An explicit n-vertex K_r-saturated graph with matching number s whose edge count falls below the stated expression for some n much larger than r and s would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.09733 by Guorong Gao, Jianfeng Hou, Yue Ma, Zian Chen.

Figure 1
Figure 1. Figure 1: The structure of G(n, 3, s) Theorem 1.1. Let s + 1 ≥ r ≥ 3 and n ≥ 63(s − 2)2 + r 2 . Then sat(n, r, s) =  (r − 1)n − r 2 (r − 1) − 1, if s = r − 1; (r − 1)n + (s − r) 2 − 1 2 (r + 2)(r − 3) − 5, if s > r − 1. Moreover, if G is an n-vertex Kr-saturated graph with matching number s and sat(n, r, s) edges, then G ∼= Kr−3 ∨ K2,n−r+1 for s = r − 1, G ∈ H(n, s) for s = r and G ∼= G(n, r, s) for s > r. The rest… view at source ↗
Figure 2
Figure 2. Figure 2: Partition of V(G) Claim 3.2. |C| ≤ (s − 3)2 . Proof. Suppose to the contrary that |C| > (s − 3)2 . Since any v ∈ C has no neighbor in C5, by Proposition 2.4, v has at least one common neighbor with each vertex of C5. For 1 ≤ i ≤ 5, denote a common neighbor of v and vi by xi . Then xi ∈ A∪B. Since A consists of vertices adjacent to exactly two vertices of C5, and B consists of vertices adjacent to exactly o… view at source ↗
Figure 3
Figure 3. Figure 3: The structure of G of G\v1. By K˝onig’s theorem (Theorem 2.3), ν(G\v1) ≤ s − 2, and thus ν(G) ≤ s − 1, a contradiction. Hence |A1,4| ≥ s − 3, and similarly |A3,5| ≥ s − 3. The extremal choice of G then gives |A1,4| = |A3,5| = s − 3. Therefore G ∼= G(n, 3, s). This completes the proof. 3.2 The case for r > 3 In this subsection, we prove the case for r ≥ 4. Let f(n, r, s) =  (r − 1)n − r 2 (r − 1) − 1, if s… view at source ↗
read the original abstract

For a clique $K_r$, a graph is $K_r$-saturated if it contains no copy of $K_r$ and the addition of any edge from its complement creates a $K_r$. A classical result of Erd\H{o}s-Hajnal-Moon and Zykov shows that the number of edges of an $n$-vertex $K_r$-saturated graph is at least $(r-2)n-\binom{r-1}{2}$. In this paper, we focus on the number of edges of the $K_r$-saturated graphs with a fixed matching number. Let $G$ be an $n$-vertex $K_r$-saturated graph with matching number $\nu(G) = s$. For sufficiently large $n$, we prove that the number of edges \begin{equation*} e(G)\geq \left\{\begin{array}{cl}{(r-1)n-\frac{r}{2}(r-1)-1,}&{\quad\mathrm{if}~s=r-1;}\\{(r-1)n + (s-r)^2 - \frac{1}{2}(r+2)(r-3) - 5,}&{\quad\mathrm{if}~s>r-1.}\\\end{array}\right. \end{equation*} Moreover, we completely characterize the graphs attaining the equality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that for an n-vertex K_r-saturated graph G with matching number ν(G)=s and n sufficiently large, e(G) is at least (r-1)n - r(r-1)/2 -1 when s=r-1 and at least (r-1)n + (s-r)^2 - (r+2)(r-3)/2 -5 when s>r-1, together with a complete characterization of the extremal graphs attaining equality. The result refines the classical Erdős–Hajnal–Moon/Zykov bound by adding the matching-number constraint.

Significance. The result strengthens the classical saturation theorem by incorporating an exact matching-number parameter and supplying both sharp bounds and explicit extremal constructions. The complete characterization of equality cases is a notable strengthening over many saturation results that only give the bound.

minor comments (3)
  1. The statement of the main theorem (presumably Theorem 1.1 or equivalent) uses the phrase 'for sufficiently large n' without an explicit lower bound on n; while standard, an effective n_0 would strengthen the result and aid verification.
  2. In the displayed bound for s>r-1, the constant term contains the factor 1/2(r+2)(r-3); confirm that the sign and the arithmetic match the derivation in the equality-case analysis (Section 3 or 4).
  3. The abstract and introduction cite the classical Erdős–Hajnal–Moon and Zykov results but do not list the precise reference numbers; add the standard citations (e.g., [EHM] and [Z]) for completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper states and proves new lower bounds on the number of edges in K_r-saturated n-vertex graphs with fixed matching number ν(G)=s, for sufficiently large n, together with equality cases. It begins from the standard definitions of K_r-saturation and matching number, invokes the classical Erdős-Hajnal-Moon/Zykov theorem as an external base case, and derives the refined bounds under the added constraint. No equation reduces a claimed prediction to a fitted parameter by construction, no self-citation is load-bearing for the central result, and no ansatz or uniqueness claim is imported from the authors' prior work. The asymptotic qualifier is conventional and does not create a definitional loop. The derivation is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definitions of cliques, matchings, and saturation; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract statement.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, cliques, matchings, and K_r-saturation.
    The paper builds directly on these classical combinatorial notions.

pith-pipeline@v0.9.1-grok · 5772 in / 1178 out tokens · 28369 ms · 2026-06-27T15:51:46.919702+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references

  1. [1]

    N. Alon, P. Erd˝ os, R. Holzman, and M. Krivelevich. Onk-saturated graphs with restrictions on the degrees.J. Graph Theory, 23(1):1–20, 1996. 4

    1996

  2. [2]

    Alon and P

    N. Alon and P. Frankl. Tur´ an graphs with bounded matching number.J. Combin. Theory Ser. B, 165:223–229, 2024. 2

    2024

  3. [3]

    K. Amin, J. Faudree, R. J. Gould, and E. Sidorowicz. On the non-(p−1)-partite Kp-free graphs.Discuss. Math. Graph Theory, 33(1):9–23, 2013. 2

    2013

  4. [4]

    A. N. Day. Saturated graphs of prescribed minimum degree.Combin. Probab. Com- put., 26(2):201–207, 2017. 2

    2017

  5. [5]

    D. A. Duffus and D. Hanson. Minimalk-saturated and color critical graphs of pre- scribed minimum degree.J. Graph Theory, 10(1):55–67, 1986. 2

    1986

  6. [6]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, and J. W. Moon. A problem in graph theory.Amer. Math. Monthly, 71:1107–1110, 1964. 2

    1964

  7. [7]

    Erd˝ os and R

    P. Erd˝ os and R. Holzman. On maximal triangle-free graphs.J. Graph Theory, 18(6):585–594, 1994. 2

    1994

  8. [8]

    Faudree, R

    J. Faudree, R. Faudree, R. Gould, and M. Jacobson. Saturation numbers for graphs: a survey.Electronic Journal of Combinatorics, 18(1):P19, 2011. 2

    2011

  9. [9]

    F¨ uredi and A

    Z. F¨ uredi and A. Seress. Maximal triangle-free graphs with restrictions on the degrees. J. Graph Theory, 18(1):11–24, 1994. 2

    1994

  10. [10]

    A. Hajnal. A theorem onk-saturated graphs.Canadian J. Math., 17:720–724, 1965. 2, 4

    1965

  11. [11]

    K´ aszonyi and Z

    L. K´ aszonyi and Z. Tuza. Saturated graphs with minimal number of edges.J. Graph Theory, 10(2):203–210, 1986. 2

    1986

  12. [12]

    D. K˝ onig. Graphok ´ es matrixok.Matematikai ´ es Fizikai Lapok, 38:116–119, 1931. Hungarian with German summary. 4 10

    1931

  13. [13]

    Zhang, H

    X. Zhang, H. Lu, and Q. Yu. A note on the minimum size of matching-saturated graphs.Discrete Appl. Math., 348:1–5, 2024. 2

    2024

  14. [14]

    A. A. Zykov. On some properties of linear complexes.Amer. Math. Soc. Translation, 1952(79):33, 1952. 2 11

    1952