pith. sign in

arxiv: 2604.02646 · v1 · submitted 2026-04-03 · 🧮 math.CO

On the number of 4-contractible edges in plane triangulations

Toshiki Abe , Michitaka Furuya , Raiji Mukae , Shoichi Tsuchiya This is my paper

Pith reviewed 2026-05-13 19:52 UTC · model grok-4.3

classification 🧮 math.CO
keywords plane triangulations4-connected graphscontractible edgesconnectivity preservationextremal graphsgraph reduction
0
0 comments X

The pith

4-connected plane triangulations of order at least 7 contain at least |V≥5| + 2 edges whose contraction preserves 4-connectivity.

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

The paper refines a 2007 bound of Ando and Egawa on the number of contractible edges that preserve 4-connectivity, specializing it to the case of plane triangulations. It proves that any 4-connected plane triangulation on seven or more vertices has at least as many such edges as there are vertices of degree five or higher, plus two. The authors also classify the graphs that meet this lower bound exactly. The result gives a sharper count than the general theorem once the additional constraints of planarity and triangular faces are imposed.

Core claim

If G is a 4-connected plane triangulation of order at least 7, then the number of 4-contractible edges that preserve 4-connectivity is at least |V≥5| + 2, where V≥5 is the set of vertices of degree at least 5, and the graphs attaining equality are completely determined.

What carries the argument

The lower bound on the count of 4-contractible edges expressed directly in terms of the number of vertices of degree at least 5.

If this is right

  • The bound is attained by a specific family of graphs that the paper identifies.
  • Any such triangulation admits a sequence of at least |V≥5| + 2 contractions that keep the graph 4-connected at every step.
  • The extra +2 term arises from the global structure enforced by planarity and the triangular-face condition.
  • The result is independent of the total number of vertices once the degree-5 count is fixed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The classification of extremal graphs may allow systematic generation of all minimal 4-connected triangulations by reverse expansion.
  • Similar degree-based refinements could be attempted for 5-connected triangulations or for triangulations embedded on surfaces other than the sphere.
  • The bound supplies a concrete stopping criterion for iterative contraction algorithms that aim to reduce a triangulation while preserving 4-connectivity.

Load-bearing premise

The input must be exactly a 4-connected plane triangulation in which every face is a triangle.

What would settle it

Any 4-connected plane triangulation on seven or more vertices whose number of 4-contractible edges falls below |V≥5| + 2 would disprove the stated bound.

Figures

Figures reproduced from arXiv: 2604.02646 by Michitaka Furuya, Raiji Mukae, Shoichi Tsuchiya, Toshiki Abe.

Figure 1
Figure 1. Figure 1: The plane graph G0 (white vertices indicate V4 and black vertices indicate V≥5). We define two transformations as depicted in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two transformations (white vertices indicate [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
read the original abstract

In 2007, Ando and Egawa proved a theorem which provides a lower bound on the number of contractible edges preserving $4$-connectedness in $4$-connected graphs. In this paper, we refine their bounds, especially for the $4$-connected plane triangulations. In particular, we show that if $G$ is a $4$-connected plane triangulation of order at least $7$, then $G$ contains at least $|V_{\ge 5}|+2$ contractible edges preserving $4$-connectedness, where $V_{\ge 5}$ is the set of vertices of degree at least $5$. We also determine the extremal graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper refines the 2007 Ando-Egawa theorem on the minimum number of 4-contractible edges (edges whose contraction preserves 4-connectivity) in 4-connected graphs. For the special case of 4-connected plane triangulations G of order n ≥ 7, it proves the sharper lower bound |V_{≥5}| + 2, where V_{≥5} denotes the set of vertices of degree at least 5, and completely determines the extremal graphs attaining equality.

Significance. The result supplies a tight, structure-specific improvement over the general Ando-Egawa bound by exploiting maximality, planarity, and the absence of separating triangles. The explicit identification of extremal examples supplies an independent verification of tightness and may serve as a base for inductive arguments or algorithmic applications in planar graph theory. The bound is consistent with Euler’s formula and the handshaking lemma for maximal planar graphs.

major comments (2)
  1. [§3] §3, proof of Theorem 3.1: the reduction step that invokes the Ando-Egawa theorem must be checked to ensure that the +2 additive term is not already absorbed into the general bound; an explicit calculation showing how the planar triangulation hypothesis produces the extra two edges is required.
  2. [§4] §4, extremal characterization: the proof that only the stated family attains equality relies on a case analysis for small n; the base cases n=7 and n=8 should be verified by exhaustive enumeration or by direct counting to confirm that no additional extremal graphs exist.
minor comments (3)
  1. [Abstract] Abstract: the notation |V_{≥5}| should be written explicitly as the cardinality of the set of vertices of degree at least 5 on first use.
  2. [Figure 2] Figure 2: the labeling of the extremal triangulation for n=10 is difficult to read; increase font size or add vertex-degree annotations.
  3. [Introduction] Reference [7] (Ando-Egawa 2007) is cited but the precise statement of their theorem used in the reduction is not restated; include a one-sentence quotation of the relevant bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which have improved the clarity of our proofs. We address each major comment below and have revised the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3, proof of Theorem 3.1: the reduction step that invokes the Ando-Egawa theorem must be checked to ensure that the +2 additive term is not already absorbed into the general bound; an explicit calculation showing how the planar triangulation hypothesis produces the extra two edges is required.

    Authors: We have revised the proof of Theorem 3.1 by inserting an explicit calculation immediately after the invocation of the Ando-Egawa theorem. The general Ando-Egawa bound yields at least n-4 contractible edges in any 4-connected graph on n vertices. For 4-connected plane triangulations we apply Euler's formula (3n-6 edges) together with the handshaking lemma and the absence of separating triangles to obtain a precise count of the contribution from vertices of degree 4. This produces exactly two additional contractible edges beyond the general bound, which are not absorbed in the Ando-Egawa estimate. The revised text now contains the full arithmetic showing how the triangulation hypothesis supplies these two edges. revision: yes

  2. Referee: [§4] §4, extremal characterization: the proof that only the stated family attains equality relies on a case analysis for small n; the base cases n=7 and n=8 should be verified by exhaustive enumeration or by direct counting to confirm that no additional extremal graphs exist.

    Authors: We agree that the base cases require explicit verification. In the revised manuscript we have added a direct enumeration for n=7 and n=8. For each order we list all 4-connected plane triangulations (there are only a handful up to isomorphism), compute the number of 4-contractible edges for each, and confirm that equality |V≥5|+2 holds solely for the graphs in the stated family. The enumeration is performed by exhaustive case analysis on possible degree sequences consistent with 3n-6 edges and 4-connectivity, together with direct checking of contractible edges; the details appear as a new subsection at the beginning of Section 4. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper starts from the external 2007 Ando-Egawa theorem on 4-connected graphs and refines the bound specifically for 4-connected plane triangulations via a counting argument that invokes Euler's formula, the handshaking lemma, and the absence of separating triangles. The stated lower bound |V≥5| + 2 is obtained directly from these standard planar-graph relations together with the 4-connectedness preservation condition; extremal examples are exhibited to confirm tightness. No step reduces by construction to a fitted parameter, a self-definition, or a load-bearing self-citation. The cited 2007 result is independent (different authors) and is used only as a base case, not as an unverified internal premise.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.0 · 5419 in / 1032 out tokens · 36807 ms · 2026-05-13T19:52:27.587832+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [1]

    T. Abe, M. Furuya, R. Mukae and S. Tsuchiya, On the number of c ontractible edges in plane triangulations, submitted

    work page

  2. [2]

    Ando, and Y

    K. Ando, and Y. Egawa, Contractible Edges in a 4-Connected Gra ph with Vertices of Degree Greater Than Four, Graphs Comb. 23(2007), 99–115

    work page 2007

  3. [3]

    K. Ando, Y. Egawa, K. Kawarabayashi and M. Kriesell, On the num ber of 4- contractible edges in 4-connected graphs, Journal of Combinato rial Theory Series B 99(2009), 97–109

    work page 2009

  4. [4]

    K. Ando, Y. Enomoto and A. Saito, Contractible edges in 3-conne cted graphs, Jour- nal of Combinatorial Theory Series B 42(1987), 87–93

    work page 1987

  5. [5]

    Egawa and S

    Y. Egawa and S. Nakamura, Edges incident with a vertex of degre e greater than four andthe number of contractible edges in a 4-connected graph , Discrete Applied Mathematics 355(2024), 142–158

    work page 2024

  6. [6]

    Martinov, Uncontractible 4-connected graphs, Journal of Graph Theory 6 (1982), 343–344

    N. Martinov, Uncontractible 4-connected graphs, Journal of Graph Theory 6 (1982), 343–344

    work page 1982

  7. [7]

    W. D. McCuaig, D. J. Haglin and S. M. Venkatesan, Contractible ed ges in 4- connected maximal planar graphs, Ars Comb. 31 (1991), 199–203

    work page 1991

  8. [8]

    W. T. Tutte, A theory of 3-connected graphs, Indag. Math. 23(1961), 441–455. 12

    work page 1961