REVIEW 1 major objections 2 minor 6 references
Order plus size of $\tau$-critical graphs
T0 review · 1 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves that every τ-critical graph G of order n with τ(G)=t satisfies |V|+|E| ≤ {t+2 choose 2}, with equality exactly for K_n (n≥2), 2K2, and C5.
desk verdict The combined bound is clean and correct, but the equality-case proof contains a false claim about 2-regular complements that needs fixing before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing tool is Hajnal's degree bound (Theorem A): in a τ-critical graph of order n with τ(G)=t, every vertex x satisfies deg_G(x) ≤ 2t−n+1. This bound is what turns the global question about the number of edges into a local degree check. Summing it over all vertices yields the edge estimate that, after adding |V|=n, reduces the combined inequality to the quadratic (n−t−1)(n−t−2) ≥ 0. The equality analysis then uses the fact that equality in the bound forces n=t+1 or n=t+2, and in the latter case the complement must be 2-regular; requiring τ-criticality forces the complement to be a single cycle of length at most five, giving the three stated extremal graphs.
What would settle it
Find a τ-critical graph G with τ(G)=t such that |V|+|E| exceeds {t+2 choose 2}. By the proof's reduction, this would require some vertex to have degree greater than 2t−n+1, so checking the maximum degree against Hajnal's bound on any candidate τ-critical graph would settle whether the claim is false.
Extended reading notes
Core claim
The central result is a sharp inequality: if G=(V,E) is a τ-critical graph of order n with transversal number τ(G)=t, then |V|+|E| ≤ {t+2 choose 2}. The proof derives this by applying Hajnal's degree bound, which states that every vertex in such a graph has degree at most 2t−n+1. Summing this bound over all vertices gives |E| ≤ n(2t−n+1)/2, and the combined quantity |V|+|E| is then at most n + n(2t−n+1)/2. A short algebraic manipulation shows this upper bound is at most {t+2 choose 2} for all n in the feasible range t+1 ≤ n ≤ 2t, with equality only when n=t+1 or n=t+2. The equality cases are then classified: n=t+1 forces a complete graph K_n, while n=t+2 forces the complement to be a single cycle of length at most five, yielding exactly 2K2 and C5.
Load-bearing premise
The proof relies entirely on Hajnal's degree bound (Theorem A), which is quoted without proof; if that bound failed for any τ-critical graph, the degree-sum step and the combined bound would not follow.
Editorial extensions
If this is right
- The combined bound immediately implies the earlier edge bound |E| ≤ {t+1 choose 2}, because |V| ≥ t+1 in any τ-critical graph.
- The equality classification gives a complete description of all τ-critical graphs that achieve the combined maximum, which may serve as a starting point for describing near-extremal graphs.
- Since the proof reduces the whole problem to a single degree-sum argument, any strengthening of Hajnal's bound would automatically produce a corresponding strengthening of the combined inequality.
- The result closes the loop on the two classical bounds (vertex and edge) by showing they are compatible in a single quadratic inequality with a clean extremal set.
- The extremal list—complete graphs, two disjoint edges, and a five-cycle—shows that the maximum is attained only by highly regular, highly symmetric examples, suggesting that τ-critical graphs with large order plus size must be tightly structured.
Reading between the lines
- A natural next step beyond the paper is to classify near-equality cases: graphs where |V|+|E| is within an additive constant of {t+2 choose 2}. Based on the proof structure, these should be graphs whose degrees are close to 2t−n+1, likely forcing a long cycle in the complement when n=t+2.
- The combined bound might extend to other criticality notions, such as edge-critical or matching-critical graphs, where analogous degree bounds are known; the same degree-sum template could yield combined bounds of the form f(t)+g(t).
- One could test the stability of the result by perturbing τ: if a graph is nearly τ-critical in the sense that τ(G−e) ≥ τ(G)−1 for most edges, does a relaxed version of the bound hold with an error term depending on the number of exceptional edges?
- The proof's dependence on Hajnal's theorem suggests that a self-contained proof of that degree bound would make the entire argument elementary and may reveal why equality occurs exactly at the three families.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. Let G=(V,E) be a τ-critical graph with τ(G)=t. The paper proves the sharp combined bound |V|+|E| ≤ binom(t+2,2), improving the classical separate bounds |V| ≤ 2t (Erdős–Gallai) and |E| ≤ binom(t+1,2) (Erdős–Hajnal–Moon). The proof sums Hajnal's degree bound deg_G(x) ≤ 2t−n+1 over all vertices, then compares the resulting quadratic expression with binom(t+2,2), showing that equality is possible only when n=t+1 or n=t+2. The equality cases are analyzed and the extremal graphs are characterized as the complete graphs K_n (n≥2), 2K2, and C5.
Significance. If the equality-case gap identified below is repaired, this is a clean and useful strengthening of classical results on τ-critical graphs. The derivation is short, essentially parameter-free, and the extremal list is explicit and checkable. The main theorem is falsifiable, and the proof is self-contained modulo the cited Hajnal theorem. However, the printed proof contains an incorrect assertion in the equality characterization that must be corrected before the paper can be accepted; the theorem itself appears true and the repair is straightforward.
major comments (1)
- [Proof of Theorem 1, equality case] The proof states: 'In the second case the candidates are the graphs whose complements are 2-regular (and have at least four vertices). Since these graphs are τ-critical with t = n−2, the deletion of any edge creates a set of three vertices inducing no edges.' The universal claim that every graph whose complement is 2-regular is τ-critical is false. For n=6, the complement of C6 (the triangular prism) has τ(G)=4=n−2, but deleting the edge of G corresponding to a distance-3 chord of C6 leaves τ(G−e)=4, not 3, so G is not τ-critical. Consequently, the stated justification of the triangle property is invalid. The desired property does follow directly from the theorem's hypothesis that G is τ-critical together with n=t+2: since τ(G−e)=t−1=n−3, we have α(G−e)=3, which means adding the corresponding chord to the 2-regular complement creates a triangle. Please rewrite this passage so that the triangle property is derived from the τ-criticality of the given graph G rather than from a false assertion about all 2-regular complements; the subsequent cycle-length reasoning is then sound.
minor comments (2)
- [Introduction, first paragraph] The phrase 'defined to be the the minimum cardinality' contains a duplicated article; it should read 'defined to be the minimum cardinality'.
- [Proof of Theorem 1, inequality (3)] The text says 'with equality if G is a (2t − n + 1)-regular graph'; this should be 'if and only if', because equality in (3) is required for the subsequent conclusion that equality in (2) forces n=t+1 or n=t+2.
Circularity Check
No circularity: the combined bound is derived from an external degree theorem (Hajnal) and the equality cases are analyzed independently; the known equality-case proof gap is a correctness issue, not a circularity.
full rationale
The derivation is self-contained conditional on the cited external Theorem A (Hajnal). The paper obtains |V|+|E| <= n + n(2t-n+1)/2 by summing degree bounds, then reduces the desired bound (2) to (n-t-1)(n-t-2) >= 0 using n >= t+1. No parameter is fitted and the target bound is not assumed. The equality-case proof contains an overgeneralization about complements of 2-regular graphs being tau-critical, but that is a mathematical error in the extremal analysis, not a circularity, because it does not presuppose the theorem or define the conclusion into the hypotheses. Citations to Lovasz and Plummer are background references, not load-bearing. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (2)
- domain assumption Hajnal's degree bound: in a τ-critical graph of order n and transversal number t, every vertex has degree at most 2t - n + 1
- domain assumption n ≥ t+1 for any τ-critical graph with no isolated vertices
Cite this review
Pith. "Pith review of Order plus size of $\tau$-critical graphs." pith.science (2026). https://pith.science/paper/7ZP4EAA7
@misc{pith2026190805225,
author = {Pith},
title = {Pith review of: Order plus size of $\tau$-critical graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/7ZP4EAA7}},
note = {Machine review of arXiv:1908.05225}
}
abstract
Let $G=(V,E)$ be a $\tau$-critical graph with $\tau(G)=t$. Erd\H{o}s and Gallai proved that $|V|\leq 2t$ and the bound $|E|\leq {t+1\choose 2}$ was obtained by Erd\H{o}s, Hajnal and Moon. We give here the sharp combined bound $|E|+|V|\leq {t+2\choose 2}$ and find all graphs with equality.
Reference graph
Works this paper leans on
-
[1]
P. Erd o s and T. Gallai, On the maximal number of vertices representing the edges of a graph, K\"ozl. MTA Mat. Kutat\'o Int. Budapest 6 (1961) 181--203
work page 1961
-
[2]
P. Erd o s, A. Hajnal, and J. W. Moon: A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107--1110
work page 1964
-
[3]
Hajnal, A theorem on k -saturated graphs, Canadian Journal of Math
A. Hajnal, A theorem on k -saturated graphs, Canadian Journal of Math. 17 (1965) 720--724
work page 1965
-
[4]
L. Lov\'asz, Combinatorial problems and exercises , Second Edition, AMS Chelsea Publishing, Providence, RI , 2007
work page 2007
-
[5]
L. Lov\'asz, and M.D. Plummer, Matching Theory . Akad\'emiai Kiad\'o, North Holland 1986
work page 1986
-
[6]
L. Sur\'anyi, On line-critical graphs, in: Infinite and Finite Sets , North Holland, Amsterdam (1975) 1411--1444
work page 1975
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.