REVIEW 1 major objections 4 minor 7 references
Light edges in 1-planar graphs of minimum degree 3
T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Every 1-planar graph of minimum degree at least 3 contains an edge whose degrees are of type (3,≤23), (4,≤11), (5,≤9), (6,≤8), or (7,7).
desk verdict Solid discharging proof that every 1-planar graph with minimum degree 3 has a light edge of one of five types; the only real caveat is a load-bearing citation for two geometric facts about false vertices. 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 central machinery is the discharging method applied to the associated plane graph $G^{\times}$ obtained by turning every crossing into a false 4-vertex. Initial charge is $d(x)-4$ for every vertex and face, so Euler's formula gives a total of $-8$. Eight rules (R1–R8) move charge from high-degree vertices and faces toward low-degree vertices; the delicate accounting objects are $k$-special false 3-faces for $k=4,5,6$ and transitive false vertices, through which faces pass charges across crossings. The proof's seven propositions check, case by case, that after redistribution every vertex and face has nonnegative charge, contradicting the negative total.
What would settle it
Find a 1-planar graph of minimum degree at least 3 with no edge of the five listed types—equivalently, every 3-vertex is surrounded only by degree-24+ vertices, every 4-vertex only by degree-12+ vertices, every 5-vertex only by degree-10+ vertices, every 6-vertex only by degree-9+ vertices, and every 7-vertex only by degree-8+ vertices. The nonexistence of such a graph is exactly Theorem 1.2. A cheaper check is the structural lemma: any 1-plane drawing containing a 3-vertex incident with two triangular faces and two crossing-generated neighbors but no face of length at least 5 would invalidate the premises on which the 3-vertex charge balance rests.
Extended reading notes
Core claim
The central claim is Theorem 1.2: each 1-planar graph of minimum degree at least 3 contains an edge of type $(3,\leq 23)$, $(4,\leq 11)$, $(5,\leq 9)$, $(6,\leq 8)$, or $(7,7)$. In words, in every such graph there is an edge whose endpoints avoid being simultaneously large, with the allowed partner degree shrinking as the smaller degree grows. The proof obtains a contradiction from the opposite assumption that every edge falls into one of the complementary high-degree types $(3,\geq 24)$, $(4,\geq 12)$, $(5,\geq 10)$, $(6,\geq 9)$, or $(\geq 7,\geq 8)$, using a discharging argument on the plane graph formed by replacing every crossing with a false 4-vertex. It then verifies that every face and vertex ends with nonnegative charge, contradicting Euler's formula fixed total of $-8$. The constants 9, 8, 7 are shown sharp; the authors state the bounds 23 and 11 may improve to 20 and 10 and pose this as an open problem.
Load-bearing premise
The load-bearing premise is that the planarized drawing obeys three structural facts borrowed from the cited reference, especially that a degree-3 vertex cannot be trapped between two crossing-generated triangular faces without also having a larger face; the discharging bookkeeping for low-degree vertices assumes these facts without proof.
Editorial extensions
If this is right
- Every 1-planar graph with minimum degree at least 3 has an edge whose two endpoints have degrees at most 23; in that sense a 'light edge' is unavoidable in the entire class.
- For graphs of minimum degree at least 4, the theorem upgrades the best previous bound for degree-4 vertices from 13 to 11, while the remaining degree-type bounds stay the same.
- The earlier light-edge result for 3-connected 1-planar graphs, which required a global connectivity condition, follows as a special case, since 3-connected implies minimum degree at least 3, though the new bound is larger (23 vs 20).
- The constants for degree 5, 6, and 7 are sharp: there are 1-planar graphs in which every light edge of that low-degree type reaches exactly the stated partner degree.
Reading between the lines
- A direct proof of the three structural facts currently imported from the cited reference would make the argument self-contained; the discharging framework itself does not otherwise depend on external results.
- The same planarization trick—replacing crossings by false vertices of even degree—combined with tailored discharging rules may extend to $k$-planar graphs for a fixed $k$, where each crossing becomes a vertex of degree $2k$ and the constants in the rules would be recomputed.
- If the conjectured sharp constants 20 and 10 are correct, then the extremal graphs already exhibited would show that the theorem is tight in all five types, and the real difficulty lies in the degree-3 and degree-4 discharge cases rather than in the existence of the light edge.
- A concrete stress test: implement the discharging rules computationally on random 1-plane graphs and check whether any final negative charge appears; a persistent negative pocket would locate where the structural lemma or the rule constants fail.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that every 1-planar graph of minimum degree at least 3 contains an edge of one of the types (3,≤23), (4,≤11), (5,≤9), (6,≤8), or (7,7). The proof uses the discharging method on the associated plane graph obtained by planarizing a minimum-crossing 1-planar drawing. The authors define explicit discharging rules and verify non-negativity of final charges for all vertices and faces through a sequence of claims and propositions. The paper also discusses sharpness of some bounds, relying on constructions from earlier literature.
Significance. If the proof is correct, this result improves the theorem of Hudák and Šugerek (minimum degree at least 4) and extends the light-edge result of Fabrici and Madaras from 3-connected 1-planar graphs to all 1-planar graphs with minimum degree 3. The discharging argument is detailed, with fully specified rules and case checks, and the main theorem is a clean structural statement. The paper is largely self-contained except for one cited structural lemma, and the sharpness discussion helpfully identifies possible improvements of the bounds 23 and 11.
major comments (1)
- [Lemma 2.1 and Proposition 2(2)(third case)] The proof of Theorem 1.2 relies crucially on Lemma 2.1(b) and (c), which are stated without proof and cited to [7, Lemma 1]. In Proposition 2(2), third case, the argument that a 3-vertex incident with two false 3-faces receives enough charge depends on (c) to identify the two false neighbors and on (b) to guarantee a 5-face that sends 2/3; without these, the available charge from the two adjacent faces via R6.1 is only 1/3, which is insufficient to make the final charge non-negative. These structural statements are delicate and their validity is tied to the minimum-crossing assumption for the 1-plane drawing; for example, a planar graph drawn with an unnecessary crossing would violate (c). The authors should either provide a full proof of (b) and (c) in this paper or give a detailed proof sketch, so that the reader is not forced to trust an external, possibly inaccessible, reference for a load-bearing step.
minor comments (4)
- [Proposition 2(3), second subcase] There is a typographical error: "v′(v)≥" should read "c′(v)≥".
- [Introduction, sharpness paragraph] The statement that the bounds 9, 8, and 7 are sharp is based on earlier constructions in [2] and [3]; it would be clearer to explicitly attribute each sharpness example to its source, since no construction is given here.
- [Rule R6.1] The phrase "to each of the elements among f2, f4, v3, v4" would be clearer if it said "to each of the faces f2 and f4 and to each of the vertices v3 and v4", to avoid possible confusion about what an "element" is.
- [Claim 3] The inequality π+(vi) ≥ 2π−(vi) is stated with "one can check" but no explanation; a short verification covering the four cases R6.1–R6.4 would improve readability.
Circularity Check
No circularity: the discharging proof is self-contained apart from independently cited structural lemmas; omitted proofs are a rigor concern, not circularity.
full rationale
The paper proves Theorem 1.2 by contradiction: it assumes no edge of the stated types exists, derives degree restrictions on neighbors, and then applies a discharging argument to the associated plane graph G^. The target theorem is never used as an input; the discharging rules are fixed constants and the contradiction comes from Euler's formula and the nonnegativity of final charges. The degree thresholds 23, 11, 9, 8, 7 appear in the special-face definitions because the contradiction hypothesis forces neighbor degrees of 24+, 12+, 10+, 9+, 8+, but this is standard contrapositive discharging, not circular fitting. The only potentially load-bearing external input is Lemma 2.1(a)-(c), quoted as '[7, Lemma 1]' from a prior paper with overlapping authorship. However, this is a separate structural lemma about 1-plane graphs, not the light-edge theorem, and it is not derived from the present result. The fact that its proof is omitted in this manuscript is a correctness/rigor risk (the charge balance for 3-vertices depends on it), but it is not a circular reduction: the cited lemma does not state or imply the theorem, and the theorem is not used to prove the lemma. Therefore no circularity is present.
Assumptions & free parameters
assumptions (4)
- standard math Euler's formula for plane graphs
- domain assumption The associated plane graph G× construction
- domain assumption Lemma 2.1(a)-(c) from Zhang and Wu [7, Lemma 1]
- domain assumption The minimal counterexample has minimum degree at least 3 and contains only edges of type (3,≥24), (4,≥12), (5,≥10), (6,≥9), or (≥7,≥8)
Cite this review
Pith. "Pith review of Light edges in 1-planar graphs of minimum degree 3." pith.science (2026). https://pith.science/paper/XHKJVV66
@misc{pith2026190805072,
author = {Pith},
title = {Pith review of: Light edges in 1-planar graphs of minimum degree 3},
year = {2026},
howpublished = {\url{https://pith.science/paper/XHKJVV66}},
note = {Machine review of arXiv:1908.05072}
}
abstract
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one another edge. In this work we prove that each 1-planar graph of minimum degree at least $3$ contains an edge with degrees of its endvertices of type $(3,\leq23)$ or $(4,\leq11)$ or $(5,\leq9)$ or $(6,\leq8)$ or $(7,7)$. Moreover, the upper bounds $9,8$ and $7$ here are sharp and the upper bounds $23$ and $11$ are very close to the possible sharp ones, which may be 20 and 10, respectively. This generalizes a result of Fabrici and Madaras [Discrete Math., 307 (2007) 854--865] which says that each 3-connected 1-planar graph contains a light edge, and improves a result of Hud\'ak and \v{S}ugerek [Discuss. Math. Graph Theory, 32(3) (2012) 545--556], which states that each 1-planar graph of minimum degree at least $4$ contains an edge with degrees of its endvertices of type $(4,\leq 13)$ or $(5,\leq 9)$ or $(6,\leq 8)$ or $(7, 7)$.
Reference graph
Works this paper leans on
-
[7]
X. Zhang, J.-L. Wu. On edge colorings of 1-planar graphs, Inform. Process. Lett. , 111(3) (2011) 124–128. 11
work page 2011
-
[1]
J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, GTM 244, 2008
work page 2008
-
[2]
I. Fabrici, T. Madaras, The structure of 1-planar graphs, Discrete Math., 307 (2007) 854–865
work page 2007
- [3]
-
[4]
S. Jendrol’, H.-J. V oss, Light subgraphs of graphs embedded in the plane — A survey, Dis- crete Math., 313 (2013) 406–421
work page 2013
-
[5]
Kotzig, Contribution to the theory of Eulerian polyhedra, Math
A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Slovaca 5 (1955) 111– 113. 10
work page 1955
-
[6]
Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh
G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. , 29 (1965) 107–117
work page 1965
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.