A characterization for graphs having strong parity factors

Hongliang Lu; Xuechun Zhang; Zixuan Yang

REVIEW 2 major objections 4 minor 15 references

A characterization for graphs having strong parity factors

T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single inequality characterizes graphs with strong parity factors.

desk verdict The paper offers a plausible new characterization and a counterexample to a recent conjecture, but the sufficiency proof of Theorem 2 rests on a false inequality in Claim 2; still worth refereeing as the gap looks repairable. read the letter →

arxiv 2009.12802 v1 pith:TK3OT2GI submitted 2020-09-27 math.CO

Hongliang Lu , Zixuan Yang , Xuechun Zhang This is my paper · ORCID

classification math.CO MSC 05C7005C40

keywords strongparitypropertyfactor(gf)-parityspanningsubgraphminimumdegreeedge-connectivitygraphcharacterization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Graphs with the strong parity property—those in which every even-sized set of vertices can be prescribed as the odd-degree vertices of a spanning subgraph with minimum degree at least one—are shown to be exactly the graphs satisfying the inequality $\sum_{x\in T} d_G(x)-2|T|-c(G-T)\ge -1$ for every vertex set $T$. The proof encodes the property as the existence of a $(g_X,f_X)$-parity factor and then applies a parity-factor existence criterion, reducing both directions to the same degree-counting condition. A corollary disproves the conjecture that every 2-edge-connected graph of minimum degree at least three has the property, and Theorem 3 shows that 3-edge-connectivity is sufficient. If correct, the characterization turns a spanning-subgraph existence question into a purely local inequality check.

What carries the argument

The carrying object is a reduction of the strong parity property to a $(g_X,f_X)$-parity factor. For a prescribed even set $X$, define $g_X(v)=-1$ and $f_X(v)=n_o$ for $v\in X$, and $g_X(v)=2$ and $f_X(v)=n_e$ for $v\notin X$, where $n_o$ and $n_e$ are the parity-matched orders; a spanning subgraph with the right parities and minimum degree at least one exists exactly when such a parity factor exists. The proof then works through the parity-factor criterion: it shows the auxiliary set $S$ can be taken empty and $T$ disjoint from $X$, reducing the criterion to the inequality in Theorem 2. The $g$-odd components counted in the criterion—components of $G-S-T$ whose internal lower-bound sum plus edges to $T$ is odd—are what connect the abstract criterion to the component count $c(G-T)$.

What would settle it

Check the unproved inequality in Claim 2 on the four-vertex path $b-u-a-d$ with $X=\{u,d\}$ and $T=\{u\}$: deleting $u$ from $T$ drops the odd-component count from 1 to 0 while $e_G(u,T)=0$, directly contradicting the asserted inequality. That observation would not disprove the theorem itself, but it would show the proof is incomplete until the step is repaired.

Watch

Extended reading notes

Core claim

The paper's central claim is a complete characterization. For every graph $G$, the strong parity property holds if and only if $\sum_{x\in T} d_G(x)-2|T|-c(G-T)\ge -1$ for all $T\subseteq V(G)$, where $c(G-T)$ is the number of connected components left after removing $T$. The sufficiency direction assumes the inequality and uses a minimal counterexample to the parity-factor criterion to force the auxiliary sets $S$ and $T$ into a normal form, yielding a contradiction. The necessity direction starts with a set $T$ violating the inequality and builds an even set $X$ from one vertex of each component with an even number of edges to $T$, with a parity adjustment, so that the chosen parity factor is forced to have an odd component and hence cannot exist. This same theorem produces a counterexample to the 2-edge-connected minimum-degree-three conjecture and proves the 3-edge-connected sufficient condition.

Load-bearing premise

The sufficiency direction rests on the unproved step that deleting a vertex from the test set $T$ cannot make the relevant odd-component count jump by more than the number of edges from that vertex to $T$; if that step fails, the characterization does not follow.

Editorial extensions

If this is right

If Theorem 2 stands, the strong parity property has a complete Tutte-type description: only degrees and component counts matter, not the detailed structure of the spanning subgraph.
An earlier conjecture is false: the paper's Corollary 5 gives a 2-edge-connected graph with minimum degree three that fails the property.
Every 3-edge-connected graph with minimum degree at least three has the strong parity property, so the failure is caused by 2-edge-connected bottlenecks rather than by low degree.
Adding edges preserves the inequality, so any edge-supergraph of a strong-parity graph is again strong-parity.
The construction used in the counterexample gives infinitely many even orders $p\ge 4$, all with the same failure mechanism.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the paper does not address: the inequality defines a set function over $T$ that looks submodular up to the component-count term; if a polynomial-time separation oracle for it exists, the strong parity property would be efficiently decidable.
The counterexample family wraps 3-regular graphs around independent subdivision vertices; one could test whether raising the minimum degree to four, while keeping 2-edge-connectivity, restores the property or whether a similar construction still breaks it.
The same $(g_X,f_X)$ encoding could be re-run with different lower bounds on the even side, yielding analogous characterizations for 'strong' variants that force minimum degree at least $k$ rather than one.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The paper's central claim is a complete characterization. For every graph $G$, the strong parity property holds if and only if $\sum_{x\in T} d_G(x)-2|T|-c(G-T)\ge -1$ for all $T\subseteq V(G)$, where $c(G-T)$ is the number of connected components left after removing $T$. The sufficiency direction assumes the inequality and uses a minimal counterexample to the parity-factor criterion to force the

/-- @claim 1 The paper's central claim is a complete characterization. For every graph $G$, the strong parity property holds if and only if $\sum_{x\in T} d_G(x)-2|T|-c(G-T)\ge -1$ for all $T\subseteq V(G)$, where $c(G-T)$ is the number of connected components left after removing $T$. The sufficiency direction assumes the inequality and uses a minimal counterexample to the parity-factor criterion to force the  -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper aims to characterize graphs with the strong parity property and to disprove a 2020 conjecture of Bujtás, Jendrol and Tuza. Theorem 2 gives an iff condition in terms of degree sums and component counts; Corollary 5 builds a 2-edge-connected counterexample; Theorem 3 gives a 3-edge-connected sufficient condition. The characterization is new, and the counterexample is explicit and convincing.

The central soft spot is in the sufficiency proof of Theorem 2, specifically Claim 2. To remove a vertex u from T, the proof asserts q(S,T') >= q(S,T) - e_G(u,T). That inequality is false. A concrete failure: take G as the path b-u-a-d plus two isolated vertices, X={u,d}, S=∅, T={u,z1,z2}. Then g_X(u)=g_X(d)=-1 and g_X=2 otherwise, so g(T)=3, degree sum over T is 2, and G-T has components {b} and {a,d}; q(S,T)=1. For T'=T-u, G-T' is the single path b-u-a-d with g_X-sum 2, so q(S,T')=0, while e_G(u,T)=0. Thus q(S,T') < q(S,T)-e_G(u,T). The displayed inequality is not merely unproved; it is false. The stress-test note observes that a nearby bound, replacing e_G(u,T) with d_{G-S}(u)-e_G(u,T)-1, might repair the argument, but that is not in the paper. Without a valid Claim 2, the proof does not establish T∩X=∅, so the sufficiency direction of Theorem 2 fails as written.

To give credit where it is due: the necessity direction looks sound, and the counterexample construction is verified by direct computation. The use of Lovász's parity factor theorem is appropriate, and the citation pattern is clean. If the gap is repaired, the result would be a solid contribution to graph factor theory.

This paper deserves a serious referee because the gap is localized and likely repairable. I would send it out, with a clear instruction that the referee may ask the authors to fix Claim 2 or supply a correct argument. As submitted, the main theorem is not established.

Referee Report

2 major / 4 minor

Summary. The paper proposes a characterization (Theorem 2) for graphs having the strong parity property: a graph G has the property if and only if for every T ⊆ V(G), the quantity sum_{x in T} d_G(x) - 2|T| - c(G-T) is at least -1, where c(G-T) is the number of connected components of G-T. The proof is built on Lovász's parity factor theorem. As applications, the authors construct a 2-edge-connected graph with minimum degree three that violates the Bujtás-Jendrol-Tuza conjecture, and prove that every 3-edge-connected graph with minimum degree at least three has the strong parity property.

Significance. If Theorem 2 is correct, it gives a clean Tutte-type characterization of the strong parity property, would disprove a published conjecture, and would imply a 3-edge-connectivity sufficient condition. The paper works within the standard Lovász parity-factor framework, and the necessity direction of Theorem 2 is largely sound. The main concern is that the sufficiency proof relies on two inequalities that are false as stated, so the central characterization is not established by the submitted arguments.

major comments (2)

[Section 2, Claim 2] The inequality q(S,T') >= q(S,T) - e_G(u,T) is false. A concrete counterexample is the path b-u-a-d together with two isolated vertices z1,z2, with X={u,d}, S=empty, and T={u,z1,z2}. Then g(T)=3, sum_{x in T} d_G(x)=2, and G-T has components {b} and {a,d}; component {b} is g-odd because g({b})+e({b},T)=2+1=3, so q(S,T)=1. For T'=T-u={z1,z2}, G-T' is the connected path on b,u,a,d with g_X-sum 2 and no edges to T', so q(S,T')=0. Since e_G(u,T)=0, the claimed inequality would give 0 >= 1, which is false. This inequality is the step used to conclude T∩X=empty, so the sufficiency direction of Theorem 2 is not proved as written.
[Section 2, Claim 1] The bound q(S',T) >= q(S,T)+d_G(v)-e_G(v,T) used in Claim 1 is also invalid. Moving v from S into the residual graph can merge several components, decreasing q rather than increasing it by the number of neighbors. For instance, in the star K_{1,3} with S={v}, T=empty, and S'=empty, q(S,T)=3 and q(S',T)=1, while d_G(v)=3 and e_G(v,T)=0, so the asserted lower bound is false. The displayed algebra also contains a sign error: the coefficient of d_G(v) is changed from negative to positive and the term 2e_G(v,T) is dropped. A correct lower bound q(S',T) >= q(S,T)+1-d_G(v)+e_G(v,T) would still yield the needed contradiction, but it is not what the paper states.

minor comments (4)

[Theorem 2 statement] The statement of Theorem 2 says that c(G-T) denotes the number of connected components of G-X; this should be G-T.
[Introduction, Theorem 1] The sentence 'If G is a connected graph, the for any X...' contains a typo: 'the' should be 'then'.
[Proof of Theorem 3] The concluding sentence says 'G have the strong parity property'; it should read 'G has the strong parity property'.
[References] Reference [8] has a formatting error: 'Springer (2010. ISBN...' should be 'Springer, 2010. ISBN...'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 2 is derived from Lovász's external parity-factor theorem and direct degree-sum checks; the skeptical Claim 2 objection is a proof-correctness issue, not a circularity.

full rationale

The paper's central characterization (Theorem 2) is proven by translating the strong parity property into the existence of (g_X, f_X)-parity factors and then invoking Lovász's standard parity-factor theorem (Theorem 4). That theorem is an external, parameter-free result and is not derived from the paper's own claims. The sufficiency direction uses a minimality argument on hypothetically violating sets S, T; the necessity direction constructs a parity set X from a hypothetical violating inequality and applies Lovász's theorem again. No fitted parameter is renamed as a prediction, and no prior work by the same authors is load-bearing: references [6] and [7] appear only in an introductory survey sentence and are not used in the proofs. The counterexample to Conjecture 1 is verified by direct degree-sum computation. The only substantive objection raised by the skeptical reading is that Claim 2's inequality q(S,T') >= q(S,T) - e_G(u,T) is asserted without proof and may be false; that is a potential mathematical error in the proof as written, not a circular reduction of the theorem to its own inputs. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The paper introduces no new free parameters or postulated entities. Its central claim rests on Lovasz's standard theorem and on the correctness of the component-counting inequalities in the proof, which are the source of the identified gap.

assumptions (1)

standard math Lovasz's (g,f)-parity factor theorem (Theorem 4) is applied to the specially chosen functions g_X and f_X.
This is a known theorem from the literature, used as a black box to translate the existence of a parity factor into the non-negativity of eta(S,T).

how reviews work

0 comments

Cite this review

Pith. "Pith review of A characterization for graphs having strong parity factors." pith.science (2026). https://pith.science/paper/TK3OT2GI

@misc{pith2026200912802,
  author       = {Pith},
  title        = {Pith review of: A characterization for graphs having strong parity factors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TK3OT2GI}},
  note         = {Machine review of arXiv:2009.12802}
}

abstract

A graph $G$ has the \emph{strong parity property} if for every subset $X\subseteq V$ with $|X|$ even, $G$ has a spanning subgraph $F$ with minimum degree at least one such that $d_F(v)\equiv 1\pmod 2$ for all $v\in X$, $d_F(y)\equiv 0\pmod 2$ for all $y\in V(G)-X$. Bujt\'as, Jendrol and Tuza (On specific factors in graphs, \emph{Graphs and Combin.}, 36 (2020), 1391-1399.) introduced the concept and conjectured that every 2-edge-connected graph with minimum degree at least three has the strong parity property. In this paper, we give a characterization for graphs to have the strong parity property and construct a counterexample to disprove the conjecture proposed by Bujt\'as, Jendrol and Tuza.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Amahashi, On factors with all degree odd, Graph Combin., 1 (1985), 111-114

A. Amahashi, On factors with all degree odd, Graph Combin., 1 (1985), 111-114

work page 1985
[2]

Cui and M

Y. Cui and M. Kano, Some results on odd factors of graphs, J. Graph Theory, 12 (1988), 327-333

work page 1988
[3]

Bujt\'as, S

C. Bujt\'as, S. Jendrol and Z. Tuza, On specific factors in graphs, Graphs and Combin., 36 (2020), 1391-1399

work page 2020
[4]

Fleischner, Spanning eulerian subgraphs, the splitting lemma, and Petersens theorem, Discrete Math., 101 (1992), 33-37

H. Fleischner, Spanning eulerian subgraphs, the splitting lemma, and Petersens theorem, Discrete Math., 101 (1992), 33-37

work page 1992
[5]

Guan, Graphic programming using odd or even points, Chinese Math., 1 (1960), 273-277

M. Guan, Graphic programming using odd or even points, Chinese Math., 1 (1960), 273-277

work page 1960
[6]

Lov\' a sz, The factorization of graphs

L. Lov\' a sz, The factorization of graphs. II, Acta Math. Acad. Sci. Hungar., 23 (1972), 223-246

work page 1972
[7]

Lu and M

H. Lu and M. Kano, Characterization of 1-tough graphs using factors, Discrete Math., 343 (2020), 111901

work page 2020
[8]

Lu and D.G.L

H. Lu and D.G.L. Wang, A Tutte-type characterization for graph factors, SIAM J. Discrete Math., 31 (2017), 1149-1159

work page 2017

Show all 15 references

[9]

Lov\' a sz, Combinatorial Problems and Exercises, North-Holland, Amsterdam (1979)

L. Lov\' a sz, Combinatorial Problems and Exercises, North-Holland, Amsterdam (1979)

1979
[10]

H. Lu, W. Wang and Y. Lin, On edge connectivity and parity factor, Acta Math. Sinica, English Series, 31 (2015), 772-776

2015
[11]

Lu and H

H. Lu and H. Liu, A degree condition for a graph to have (a,b)-parity factors, Discrete Math., 341 (2018), 244-252

2018
[12]

Lu and Y

H. Lu and Y. Lin, Note on parity factors of regular graphs, Electronic J. Graph Theory and Applications, 1 (2013) ,50-55

2013
[13]

Petersen, Die Theorie der regul\" a en Graphen

J. Petersen, Die Theorie der regul\" a en Graphen. Acta Math., 15 (1891), 193-220
[14]

Yu and G

Q. Yu and G. Liu, Graph Factors and Matching Extensions, Springer (2010. ISBN: 9783540-939511) (print)

2010
[15]

A.Kotlov, Short Proof of the Gallai-Edmonds Structure Theorem, arXiv:math.Co/0011204 v1, Nov. 2000

2000

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

Amahashi, On factors with all degree odd, Graph Combin., 1 (1985), 111-114

A. Amahashi, On factors with all degree odd, Graph Combin., 1 (1985), 111-114

work page 1985

[2] [2]

Cui and M

Y. Cui and M. Kano, Some results on odd factors of graphs, J. Graph Theory, 12 (1988), 327-333

work page 1988

[3] [3]

Bujt\'as, S

C. Bujt\'as, S. Jendrol and Z. Tuza, On specific factors in graphs, Graphs and Combin., 36 (2020), 1391-1399

work page 2020

[4] [4]

Fleischner, Spanning eulerian subgraphs, the splitting lemma, and Petersens theorem, Discrete Math., 101 (1992), 33-37

H. Fleischner, Spanning eulerian subgraphs, the splitting lemma, and Petersens theorem, Discrete Math., 101 (1992), 33-37

work page 1992

[5] [5]

Guan, Graphic programming using odd or even points, Chinese Math., 1 (1960), 273-277

M. Guan, Graphic programming using odd or even points, Chinese Math., 1 (1960), 273-277

work page 1960

[6] [6]

Lov\' a sz, The factorization of graphs

L. Lov\' a sz, The factorization of graphs. II, Acta Math. Acad. Sci. Hungar., 23 (1972), 223-246

work page 1972

[7] [7]

Lu and M

H. Lu and M. Kano, Characterization of 1-tough graphs using factors, Discrete Math., 343 (2020), 111901

work page 2020

[8] [8]

Lu and D.G.L

H. Lu and D.G.L. Wang, A Tutte-type characterization for graph factors, SIAM J. Discrete Math., 31 (2017), 1149-1159

work page 2017