{"id":"18ede224-6681-49aa-954d-15aa86606d90","arxiv_id":"1908.05225","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every τ-critical graph with transversal number t satisfies |V|+|E| ≤ C(t+2,2), with equality exactly for K_n (n≥2), 2K2, and C5.","lead":"The paper proves a new sharp inequality for graphs where deleting any edge lowers the minimum vertex cover size: vertices plus edges is at most the binomial coefficient (t+2 choose 2), with t the vertex cover number. The only graphs reaching the bound are complete graphs, two disjoint edges, and the five-cycle.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equality-case proof falsely asserts all (n-3)-regular graphs with 2-regular complement are τ-critical; e.g., complement of C6 is not, so the proof of the equality characterization is invalid as written.","rationale":"The reader's weakest_assumption focused on reliance on Hajnal's degree bound, which is an external theorem and likely correct. My stress-test identifies a different, internal flaw: the equality-case proof contains a false universal claim about (n−3)-regular graphs with 2-regular complements. This does not refute the main upper bound or the stated equality characterization—the argument can be repaired by deriving the edge-deletion property directly from τ-criticality and then applying the cycle-length constraints. But because the proof as written is invalid at a load-bearing step, the reader's unconditional ACCEPT with HIGH confidence should be adjusted to conditional acceptance pending a corrected proof of the equality cases. The concrete test (checking the triangular prism) settles that the asserted universal property is false, confirming the concern lands.","tokens_in":1755,"tokens_out":17068,"duration_ms":170863,"concrete_test":"Compute the deletion property for the triangular prism, the complement of C6: n=6, degree 3, τ=4=n−2. Delete the edge corresponding to a distance-3 chord of C6 and check whether the independence number increases from 2 to 3. If it does not (τ remains 4), the graph is not τ-critical, directly falsifying the proof's assertion that all 2-regular-complement candidates are τ-critical with t=n−2.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1, after establishing that equality in (2) forces n=t+1 or n=t+2, the paper 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 is false. For n=6, take H=C6; its complement G is the triangular prism, which is 3-regular with τ(G)=4=n−2, but G is not τ-critical: deleting the edge corresponding to a distance-3 chord of C6 leaves τ(G−e)=4, not 3. Equivalently, adding that chord to C6 creates no triangle, so G−e has no independent set of size 3. For n=7, the complement of C7 is 4-regular with τ=4≠5, so it is not even a candidate for t=n−2. The proof uses the false assertion to derive the 'edge deletion creates an independent triple' property for all 2-regular-complement graphs. That property is true for the actual τ-critical graphs under consideration, and the subsequent cycle-length argument (single cycle, length at most 5) is correct, so the theorem itself is likely true. However, the proof as written contains a genuine mathematical error in the equality-case characterization and needs a repair.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":2072,"tokens_out":6539,"duration_ms":63335,"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":[{"comment":"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.","section":"Proof of Theorem 1, equality case"}],"minor_comments":[{"comment":"The phrase 'defined to be the the minimum cardinality' contains a duplicated article; it should read 'defined to be the minimum cardinality'.","section":"Introduction, first paragraph"},{"comment":"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.","section":"Proof of Theorem 1, inequality (3)"}],"recommendation":"major_revision","confidential_remarks":"The error in the equality-case proof is isolated and fixable; the theorem and the overall strategy appear correct. After the authors replace the false universal assertion with the argument based on the τ-criticality of the given graph, I would support acceptance. The paper is consistent with the journal's scope and the result is a nice strengthening of classical bounds. My major_revision recommendation reflects the fact that a load-bearing step in the proof as printed is invalid, not any doubt about the theorem itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real: for a τ-critical graph with τ(G)=t, the paper proves |V|+|E| ≤ C(t+2,2), which sharpens the two classical bounds of Erdős–Gallai and Erdős–Hajnal–Moon. The proof is a short, transparent application of Hajnal's degree bound plus a quadratic inequality, and that part is correct. The extremal list (K_n, 2K2, C5) is also very likely correct. So the paper deserves a serious referee, not a desk reject.\n\nThe soft spot is in the equality-case proof. After deriving that equality forces n=t+1 or n=t+2, the paper says all graphs whose complements are 2-regular are τ-critical with t=n−2. That is false. Take n=6: the complement of C6 is the triangular prism, which has τ=4=n−2 but is not τ-critical—delete the edge corresponding to a distance-3 chord of C6, and τ stays 4. The paper then uses that false claim to assert that deleting any edge creates an independent triple. The correct route is to use τ-criticality of the actual G: because τ(G)=n−2, deleting any edge must drop τ to n−3, which is exactly the property of creating an independent set of size 3. That property, applied to the complement, does imply the complement is a single cycle of length at most 5, and the final classification goes through. So the theorem is salvageable, but the proof as written has a genuine gap.\n\nI checked the rest for circularity or invented entities. There are none. The derivation is self-contained given the cited Hajnal theorem, which is an external standard result; quoting it without proof is fine.\n\nThe paper is short, the main inequality is useful and the characterization is complete after repair. The false universal should be caught in peer review, and the authors will need to rewrite that part. I'd still accept it for review; the fix is minor-to-moderate and the core result stands.","headline":"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.","tokens_in":2576,"tokens_out":3965,"would_cite":false,"duration_ms":41822,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["τ-critical graphs","transversal number","vertex cover","extremal graph theory","combined order and size bound","Hajnal degree bound","equality cases"],"falsifier":"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.","tokens_in":1601,"feed_emoji":"📐","tokens_out":2514,"duration_ms":25990,"temperature":0.7,"pith_summary":"The paper answers a natural extremal question: for graphs that are minimally imperfect with respect to the vertex-cover number, how large can the sum of the number of vertices and edges be? It establishes the sharp bound |V|+|E| ≤ {t+2 choose 2} for every τ-critical graph with τ(G)=t, improving the separate bounds |V| ≤ 2t and |E| ≤ {t+1 choose 2} by combining them into a single inequality. A sympathetic reader should care because such combined bounds often expose structure that separate bounds hide; here the extremal graphs turn out to be exactly three simple families: complete graphs, a disjoint union of two edges, and a five-cycle.","feed_headline":"Critical graphs capped by a combined size bound","feed_subtitle":"Order plus edges is at most (t+2 choose 2); equality only on cliques, 2K2, and C5.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the degree bound deg_G(x) ≤ 2t−n+1 for τ-critical graphs, which is the main engine of the proof.","marker":"[3]"},{"why":"Establishes the vertex bound |V| ≤ 2t, one of the two classical inequalities that the combined bound refines.","marker":"[1]"},{"why":"Establishes the edge bound |E| ≤ {t+1 choose 2}, the other classical inequality that the combined bound extends.","marker":"[2]"}],"fun_headline_variants":["Sharp bound on order plus size for τ-critical graphs","Critical graphs: |V|+|E| capped at (t+2 choose 2)","Tight sum bound for τ-critical graphs with equality cases","Order plus edges maximized only on cliques, 2K2, C5 in τ-critical graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sharp bound on order plus size for τ-critical graphs","Critical graphs: |V|+|E| capped at (t+2 choose 2)","Tight sum bound for τ-critical graphs with equality cases","Order plus edges maximized only on cliques, 2K2, C5 in τ-critical graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000948,"raw_usage":{"total_tokens":3994,"prompt_tokens":838,"completion_tokens":3156,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":3073}},"tokens_in":454,"tokens_out":3156,"duration_ms":25053,"temperature":1.0,"reasoning_tokens":3073,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:39:18.544911+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Hajnal, A theorem on k -saturated graphs, Canadian Journal of Math","cited_arxiv_id":null,"evidence_quote":"Supplies the degree bound deg_G(x) ≤ 2t−n+1 for τ-critical graphs, which is the main engine of the proof."},{"cited_title":"Erd o s and T","cited_arxiv_id":null,"evidence_quote":"Establishes the vertex bound |V| ≤ 2t, one of the two classical inequalities that the combined bound refines."},{"cited_title":"Erd o s, A","cited_arxiv_id":null,"evidence_quote":"Establishes the edge bound |E| ≤ {t+1 choose 2}, the other classical inequality that the combined bound extends."}],"review_version":1}