pith. sign in

arxiv: 2210.04424 · v2 · submitted 2022-10-10 · 🧮 math.CO

Spanning bipartite quadrangulations of triangulations of the projective plane

Kenta Noguchi This is my paper

Pith reviewed 2026-05-24 10:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords spanning subgraphbipartite quadrangulationtriangulationprojective planecombinatorial characterizationgraph embeddingnon-orientable surfacetopological graph theory
0
0 comments X

The pith

Triangulations of the projective plane have spanning bipartite quadrangulation subgraphs exactly when they satisfy a combinatorial characterization.

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

The paper completely characterizes triangulations of the projective plane that contain a spanning bipartite quadrangulation subgraph. This supplies an affirmative answer to the 2002 question of Kündgen and Ramamurthi, but only for the projective planar case. The characterization rests on combinatorial and topological properties of the triangulation on this surface. A reader cares because it settles precisely which triangulations admit the subgraph rather than leaving the question open or requiring extra structure.

Core claim

We completely characterize triangulations of the projective plane that have a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by Kündgen and Ramamurthi for the projective planar case.

What carries the argument

The spanning bipartite quadrangulation subgraph of a triangulation on the projective plane, together with the combinatorial conditions that decide its existence.

If this is right

  • The property holds precisely for those triangulations meeting the identified combinatorial conditions.
  • The 2002 question receives an affirmative resolution in the projective planar setting.
  • No additional structure beyond the embedding on the projective plane is needed for the decision.
  • The result applies uniformly to all triangulations of this surface that pass the test.

Where Pith is reading between the lines

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

  • The same style of characterization might be attempted for triangulations on the Klein bottle or other non-orientable surfaces.
  • The conditions could support a polynomial-time recognition procedure for the property.
  • The result may connect to questions about spanning subgraphs with prescribed face lengths on surfaces.

Load-bearing premise

That the existence of the spanning subgraph can be decided from the combinatorial and topological properties of the triangulation on the projective plane alone.

What would settle it

A triangulation of the projective plane that either has a spanning bipartite quadrangulation but fails the stated conditions or lacks one while satisfying them.

Figures

Figures reproduced from arXiv: 2210.04424 by Kenta Noguchi.

Figure 1
Figure 1. Figure 1: Left: K6 on P. Right: G constructed from K6 and T1; T5; T6. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Quasi-Eulerian triangulation T1 w.r.t.f1 constructed from E1 and T11; T12. Ei properly by red and blue such that fi is red. Let ri1, ri2, . . . , riki be all red faces of Ei other than fi . Let Ri1, . . . , Riki be plane triangulations and r 0 ij ∈ F(Rij ) for j ∈ {1, . . . , ki} (possibly Rij = ∅ for each j). Further, let bi1, bi2, . . . , bi(ki+1) be all blue faces of Ei . Let Bi1, . . . , Bi(ki+1) be qu… view at source ↗
Figure 3
Figure 3. Figure 3: 4-contraction and a 2-vertex removal. Matsumoto et al. [11] proved the following generating theorem for Eulerian multitriangu￾lations of the torus, which describes how to generate them. Note that, by Euler’s formula, every Eulerian multitriangulation G of the torus has a 2- or 4-vertex unless G is a 6-regular triangulation. Theorem 26 (Matsumoto et al. [11]). Every Eulerian multitriangulation of the torus … view at source ↗
Figure 4
Figure 4. Figure 4: 6-contraction of v at {v2, v4, v6} [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: {5, 5}-contraction of u; v at {v1, v2, v4, v5}. The existence of spanning bipartite quadrangulations in triangulations can be preserved through three operations as described in the following lemma. Lemma 27. Let G be a multitriangulation of a surface Σ, and G0 be a multitriangulation of Σ obtained from G by a 4-contraction, 6-contraction, or {5, 5}-contraction. If G0 has a spanning bipartite quadrangulatio… view at source ↗
Figure 6
Figure 6. Figure 6: (Sub)graph X. On the right-hand side, the color of v3 is either black or white. Proof of Theorem 6. First, we show the “if” part. If G = K6, then G is a triangulation by Fact 11 (see the left-hand side of [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: K6 and a triangulation of P. Next, we show the “only if” part. First, we suppose that G has K6 as a subgraph. By the assumption, there exists at least one triangle C of K6 bounding a 2-cell region such that 12 [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: ). Thus, G00 does not have K6 unless G contains X. By Lemma 30, G cannot contain X, and hence G00 does not have K6. Then, G00 has a spanning bipartite quadrangulation by the minimality of G, and so does G by Lemma 27, which is a contradiction [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Subgraph Y in Case (2-3). The shaded region includes some edges and possibly vertices. Case (3) There exist two adjacent 5-vertices u, v in G. (Assume that there are no 4-vertices in G.) Let v1, v2, v3, v4 (resp. v4, v5, v6, v1) be the neighbors of v (resp. u) in G in this order. We may assume that one of the following three cases occurs because of the symmetry. (3-1) v2 = v5 and v3 = v6. In this case, G h… view at source ↗
Figure 6
Figure 6. Figure 6: Subsequently, G has a weak 2-coloring by Lemma 30, and G has a spanning bipartite quadrangulation by Proposition 2, which is a contradiction. (3-2) v2 = v5 and v3 6= v6. In this case, {5, 5}-contraction of u; v at {v1, v3, v4, v6} can be applied. Let G00 be the resulting triangulation. Note that since there exist no separating 3- cycles in G, the resulting 3-cycle v2u 00v 00 should be noncontractible in G0… view at source ↗
Figure 10
Figure 10. Figure 10: Graphs Z and Z 0 in Case (3-2). G0 . Let u1, . . . , u5 be the vertices of K6 other than v 0 in G0 appearing clockwise around v 0 . By Fact 11, u1, . . . , u5 form a contractible 5-cycle in G0 (and hence in G). Note that v2, v3, v4, v6 may coincide with ui . Let T be a near-triangulation consisting of the 5-cycle u1 · · · u5 and its inner vertices and edges in G. Since u1u 0 , . . . , u5u 0 ∈ E(G0 ), v1 o… view at source ↗
Figure 11
Figure 11. Figure 11: Subgraph X in Case (3-3a). The shaded regions include some edges and possibly vertices. In the right-hand side, possibly v2 = u4 and/or v6 = u1. (3-3b) G does not have K5 as a subgraph. In this case, both u 0 and v 0 (resp. u 00 and v 00) should be vertices of K6 in G0 (resp. G00). Let u1, u2, u3, u4 be the vertices of K6 other than u 0 and v 0 in G0 . By Fact 11, without loss of generality, u and v are i… view at source ↗
Figure 12
Figure 12. Figure 12: K4 in Case (3-3b). Left: the shaded region should contain edges u2v1 and u3v1; Right: the shaded region should contain edges u1v6 and, hence, u3v5 and u2v6 but impossible. From (1)–(3), such a counterexample G does not exist, and the proof is completed. Proof of Theorem 7. Let G be a triangulation of a surface. Since any bipartite subgraph H of G cannot contain all three edges of a triangular face, |E(H)|… view at source ↗
read the original abstract

We completely characterize triangulations of the projective plane that have a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by K\"undgen and Ramamurthi (J Combin Theory Ser B 85, 307--337, 2002) for the projective planar case.

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

0 major / 0 minor

Summary. The paper claims to completely characterize triangulations of the projective plane that admit a spanning bipartite quadrangulation subgraph. This supplies an affirmative answer to the 2002 question of Kündgen and Ramamurthi in the projective-planar setting, expressed in terms of combinatorial and topological properties of the triangulation.

Significance. If the characterization holds, the result is significant: it resolves an open question on spanning subgraphs of embedded triangulations by supplying an explicit, checkable condition that depends only on the triangulation itself. The work thereby contributes a concrete advance in the study of quadrangulations and bipartite spanning subgraphs on non-orientable surfaces.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its significance in resolving the Kündgen–Ramamurthi question for the projective plane, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; characterization is self-contained

full rationale

The paper presents a complete combinatorial characterization of triangulations of the projective plane admitting a spanning bipartite quadrangulation subgraph, directly resolving an external 2002 question by Kündgen and Ramamurthi. No equations, fitted parameters, or reductions to self-defined quantities appear in the provided abstract or claim. The central result relies on standard graph-theoretic and topological arguments on surfaces rather than any self-citation chain, ansatz smuggling, or renaming of known results. The derivation is therefore independent of its inputs and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of triangulations, bipartite graphs, and quadrangulations on surfaces from prior combinatorial literature; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of triangulation, spanning subgraph, bipartite graph, and quadrangulation in the context of embeddings on the projective plane.
    The abstract invokes these combinatorial objects without redefining them.

pith-pipeline@v0.9.0 · 5555 in / 1196 out tokens · 22298 ms · 2026-05-24T10:43:41.442571+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P. Zumstein, Polychromatic colorings of plane graphs, Discrete Comput. Geom. 42 (2009) 421–442

    work page 2009

  2. [2]

    Appel, W

    K. Appel, W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712

    work page 1976

  3. [3]

    B¨ abler, ¨Uber die zerlegung regul¨ arer streckenkomplexe ungerader ordnung, Comment

    F. B¨ abler, ¨Uber die zerlegung regul¨ arer streckenkomplexe ungerader ordnung, Comment. Math. Helvetici 10 (1938) 275–287

    work page 1938

  4. [4]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, New York, 2008

    work page 2008

  5. [5]

    J. Czap, M. Horˇ n´ ak, S. Jendrol’, A survey on the cyclic coloring and its relaxations, Discuss. Math. Graph Theory 41 (2021) 5–38

    work page 2021

  6. [6]

    Fijavˇ z, A

    G. Fijavˇ z, A. Nakamoto, Odd complete minors in even embeddings on surfaces, Discrete Math. 339 (2016) 165–178

    work page 2016

  7. [7]

    K¨ undgen, R

    A. K¨ undgen, R. Ramamurthi, Coloring face-hypergraphs of graphs on surfaces, J. Combin. Theory Ser. B 85 (2002) 307–337

    work page 2002

  8. [8]

    K¨ undgen, C

    A. K¨ undgen, C. Thomassen, Spanning quadrangulations of triangulated surfaces, Abh. Math. Semin. Univ. Hambg. 87 (2017) 357–368

    work page 2017

  9. [9]

    W. Liu, S. Lawrencenko, B. Chen, M.N. Ellingham, N. Hartsfield, H. Yang, D. Ye, X. Zha, Quadrangular embeddings of complete graphs and the even map color theorem, J. Combin. Theory Ser. B 139 (2019) 1–26

    work page 2019

  10. [10]

    Lukot’ka, E

    R. Lukot’ka, E. Rollov´ a, Perfect matchings of regular bipartite graphs, J. Graph Theory 85 (2017) 525–532

    work page 2017

  11. [11]

    Matsumoto, A

    N. Matsumoto, A. Nakamoto, T. Yamaguchi, Generating even triangulations of the torus, Discrete Math. 341 (2018) 2035–2048

    work page 2018

  12. [12]

    Mohar, P.D

    B. Mohar, P.D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B 84 (2002) 301–310. 18

    work page 2002

  13. [13]

    Mohar, C

    B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore and London, 2001

    work page 2001

  14. [14]

    Nakamoto, K

    A. Nakamoto, K. Noguchi, K. Ozeki, Cyclic 4-colorings of graphs on surfaces, J. Graph Theory 82 (2016) 265–278

    work page 2016

  15. [15]

    Nakamoto, K

    A. Nakamoto, K. Noguchi, K. Ozeki, Spanning bipartite quadrangulations of even triangu- lations, J. Graph Theory 90 (2019) 267–287

    work page 2019

  16. [16]

    Negami, Unique and faithful embeddings of projective-planar graphs, J

    S. Negami, Unique and faithful embeddings of projective-planar graphs, J. Graph Theory 9 (1985) 235–243

    work page 1985

  17. [17]

    Negami, Uniqueness and faithfulness of embeddings of toroidal graphs, Discrete Math

    S. Negami, Uniqueness and faithfulness of embeddings of toroidal graphs, Discrete Math. 44 (1983) 161–180

    work page 1983

  18. [18]

    Noguchi, Even embeddings of the complete graphs and their cycle parities, J

    K. Noguchi, Even embeddings of the complete graphs and their cycle parities, J. Graph Theory 85 (2017) 187–206

    work page 2017

  19. [19]

    Plesn´ ık, Remarks on regular factors of regular graphs, Czechoslovak Math

    J. Plesn´ ık, Remarks on regular factors of regular graphs, Czechoslovak Math. J. 24 (1974) 292–300. 19

    work page 1974