{"id":"224479c0-38a9-4286-8406-b755ac18ca5c","arxiv_id":"1908.05072","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every 1-planar graph of minimum degree at least 3 contains an edge of type (3,≤23), (4,≤11), (5,≤9), (6,≤8), or (7,7).","lead":"This paper proves that every 1-planar graph with minimum degree at least 3 contains an edge whose endpoints have bounded degrees, for example a degree-3 vertex joined to a vertex of degree at most 23. The proof uses a discharging argument, a standard tool in graph theory, and improves earlier results that required minimum degree at least 4.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof relies on unproved structural facts Lemma 2.1(b),(c) cited to [7]; if either fails, the discharging balance for 3-vertices in Proposition 2 collapses.","rationale":"After reading the full proof, I find the case analysis internally consistent under Lemma 2.1. The reader's weakest-assumption is correct: the only imported structural input is Lemma 2.1(b),(c). I did not find a more serious internal inconsistency; Claim 3's inequalities, the face-charge estimates, and the vertex-case analyses all check out, with some terse case splits that are standard. The load-bearing nature is clear: a counterexample to (b) or (c) would directly break Proposition 2(2) third and prevent the global negative-sum contradiction. Since the cited lemma is published, this is a verification concern rather than evidence of falsehood; therefore the reader's ACCEPT verdict can stand, but the paper would be strengthened by reproducing the proof or stating the lemma in full. If verification of [7] were to fail, the verdict should move to CONDITIONAL or REJECT; on current evidence, UNCHANGED.","tokens_in":11735,"tokens_out":42641,"duration_ms":405769,"concrete_test":"Obtain [7, Lemma 1] and check that it proves exactly Lemma 2.1(a)-(c) under the same definition of 1-plane graph (a 1-planar drawing with minimum number of crossings), with no additional hypothesis such as 2-connectivity or minimum degree at least 4. Then independently re-derive the local configuration in Proposition 2(2) third: a true 3-vertex v with two false 3-faces and false neighbors v1 and v3; verify from the crossing structure that the third face is indeed 5+ and that the two faces across v1v2 and v2v3 send at least 1/6 each via R6.1. If the cited lemma or that derivation fails, the discharge of 3-vertices needs repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central discharging argument is a contradiction proof. A true 3-vertex with two false 3-faces is handled in Proposition 2(2) third via Lemma 2.1(b),(c): (c) forces the false vertices to be the two non-shared neighbors v1 and v3, and (b) forces the remaining face f3 to have length at least 5, guaranteeing the 2/3 charge from R8. In the same subcase, the R6.1 charges of at least 1/6 each from h1 and h2 depend on the same identification. If (b) or (c) is not valid for the chosen minimum-crossing 1-plane drawing, the only charges available to v are 2 x 1/6 = 1/3, while the initial charge is -1; balance fails and the contradiction is not obtained. The manuscript gives no proof of these facts, only says they come from [7, Lemma 1]. Lemma 2.1(a) follows from each edge crossing at most once, but (b) and (c) are nontrivial geometric assertions about crossings near a degree-3 vertex. This is the least secure load-bearing step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11948,"tokens_out":28122,"duration_ms":244294,"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":[{"comment":"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.","section":"Lemma 2.1 and Proposition 2(2)(third case)"}],"minor_comments":[{"comment":"There is a typographical error: \"v′(v)≥\" should read \"c′(v)≥\".","section":"Proposition 2(3), second subcase"},{"comment":"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.","section":"Introduction, sharpness paragraph"},{"comment":"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.","section":"Rule R6.1"},{"comment":"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.","section":"Claim 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid discharging proof and the main result is plausible. The only substantive concern is the reliance on Lemma 2.1(b) and (c) from a cited paper without proof. If the authors can adequately justify these statements—either by proof or by a very explicit quotation with the necessary context—I would be inclined to accept. The remaining issues are minor."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main theorem is new and worth knowing: every 1-planar graph of minimum degree at least 3 contains an edge of type (3,≤23), (4,≤11), (5,≤9), (6,≤8), or (7,7). It improves Hudák–Šugerek's 13 to 11 for 4-vertices, and it extends Fabrici–Madaras from the 3-connected case to all minimum-degree-3 graphs. The discharging proof is long but carefully specified; I spot-checked several of the key inequalities in Claims 1–5 and Propositions 1–6 and found no arithmetic errors. The argument is a genuine contradiction from Euler's formula with explicit rules, not a fitted derivation.\n\nWhat the paper does well: the discharging rules are deliberately more elaborate than earlier work because they have to handle 3-vertices adjacent to crossings, which prior minimum-degree-4 arguments could avoid. The sharpness statements for the 9, 8, and 7 bounds are included, and the authors are honest that 23 and 11 may be improvable to 20 and 10, posing that as Problem 1.3. That is the right way to handle bounds you cannot yet nail.\n\nThe soft spot is exactly what the stress-test note flags: the proof depends on Lemma 2.1(b) and (c), taken without proof from Zhang–Wu [7]. These structural facts about a 3-vertex incident with two 3-faces and adjacent to two false vertices are load-bearing in Proposition 2(2), third case. If either were false, the charge balance for that 3-vertex would collapse, and the contradiction would not follow. This is the least secure step in the paper. However, it is a citation to a published source, not an omitted proof of an original claim; part (a) is elementary and part (d) is proved in the text. A referee should verify the cited lemma and, ideally, ask the authors to include a proof or a more precise pointer to keep the paper self-contained. That is a minor-to-moderate concern, not a fatal one. The rest of the proof checks out as far as I can see.\n\nThis is a solid subfield contribution. It deserves a serious referee and likely acceptance after the cited lemma is checked. I would cite it if I worked on light subgraphs in 1-planar graphs, and it is worth bringing to a graph theory reading group.","headline":"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.","tokens_in":12462,"tokens_out":2180,"would_cite":true,"duration_ms":22692,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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).","keywords":["1-planar graph","light edge","discharging method","minimum degree 3","associated plane graph","degree types","edge degree bounds","structural graph theory"],"falsifier":"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.","tokens_in":11524,"feed_emoji":"📐","tokens_out":9890,"duration_ms":91052,"temperature":0.7,"pith_summary":"This paper proves that if a 1-planar graph—one that can be drawn in the plane so that every edge crosses at most one other edge—has every vertex of degree at least 3, then it must contain a light edge: an edge whose two endpoints are not both high-degree. Concretely, one endpoint has degree 3, 4, 5, 6, or 7 and the other endpoint has degree no more than 23, 11, 9, 8, or 7 respectively. This settles the natural minimum-degree-3 version of a question previously answered only for 3-connected 1-planar graphs or for minimum degree at least 4. The proof also shows that the bounds 9, 8, 7 are best possible, and leaves 23 and 11 close to what might be the true sharp values 20 and 10.","feed_headline":"Every 1-planar graph of minimum degree 3 has a light edge","feed_subtitle":"A discharging proof shows one edge always pairs a degree-3 through degree-7 vertex with a bounded neighbor.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the structural Lemma 2.1 facts about false vertices and low-degree faces on which the discharge balance for 3- and 4-vertices relies.","marker":"[7]"},{"why":"Provides the previous minimum-degree-4 light-edge theorem being improved and the extremal graphs with only (4,10)/(10,10) edges.","marker":"[3]"},{"why":"Proves the 3-connected 1-planar light-edge theorem and supplies the (3,20)/(20,20) extremal graph that motivates the target bound 20.","marker":"[2]"}],"fun_headline_variants":["Every 1-planar graph with min degree 3 has a light edge","Min degree 3 ensures light edge in 1-planar graphs","Light edge guaranteed in 1-planar graphs of min degree 3","1-planar graphs with min degree 3 always have a light edge"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Every 1-planar graph with min degree 3 has a light edge","Min degree 3 ensures light edge in 1-planar graphs","Light edge guaranteed in 1-planar graphs of min degree 3","1-planar graphs with min degree 3 always have a light edge"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001499,"raw_usage":{"total_tokens":6057,"prompt_tokens":1033,"completion_tokens":5024,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":649,"completion_tokens_details":{"reasoning_tokens":4945}},"tokens_in":649,"tokens_out":5024,"duration_ms":33078,"temperature":1.0,"reasoning_tokens":4945,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:23:44.422340+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Zhang, J.-L","cited_arxiv_id":null,"evidence_quote":"Supplies the structural Lemma 2.1 facts about false vertices and low-degree faces on which the discharge balance for 3- and 4-vertices relies."},{"cited_title":"Hudák, P","cited_arxiv_id":null,"evidence_quote":"Provides the previous minimum-degree-4 light-edge theorem being improved and the extremal graphs with only (4,10)/(10,10) edges."},{"cited_title":"Fabrici, T","cited_arxiv_id":null,"evidence_quote":"Proves the 3-connected 1-planar light-edge theorem and supplies the (3,20)/(20,20) extremal graph that motivates the target bound 20."}],"review_version":1}