pith. sign in

arxiv: 2605.17515 · v1 · pith:YZV3SH3Ynew · submitted 2026-05-17 · 🧮 math.CO

Rooted bicubic planar maps via Dyck paths

Juan B. Gil , Jackie N. Kaminski This is my paper

Pith reviewed 2026-05-19 22:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords bicubic planar mapsDyck pathsbijection3-connected componentsTutte decompositioncombinatorial enumerationrooted maps
0
0 comments X

The pith

Rooted bicubic planar maps on 2n vertices correspond bijectively to Dyck paths of semilength 3n with colored ascents of length divisible by 3.

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

The paper establishes an explicit bijection between rooted bicubic planar maps and specific colored Dyck paths. This shows how to construct every map by choosing a Dyck path and then coloring its long ascents with the appropriate 3-connected blocks. A reader would care because the bijection makes the decomposition into 3-connected components fully constructive and combinatorial rather than algebraic. If correct, it allows assembling maps directly from their irreducible parts without solving equations.

Core claim

We provide a combinatorial proof of Tutte's decomposition of rooted bicubic planar maps into 3-connected components. We establish an explicit bijection between rooted bicubic planar maps on 2n vertices and Dyck paths of semilength 3n with ascents of length divisible by 3, where each 3j-ascent is colored using one of g_j colors corresponding to the rooted 3-connected bicubic maps on 2j vertices. Our bijection gives a constructive method for assembling all rooted bicubic planar maps from their 3-connected building blocks. We also give a simple proof that every 3-connected bicubic planar map on 2n vertices with n ≥ 4 can be obtained from a smaller primitive map through just two insertion 4 or 6

What carries the argument

The explicit bijection mapping each map to a Dyck path whose ascents of length 3j are colored by choices of 3-connected maps on 2j vertices.

Load-bearing premise

The numbers of rooted 3-connected bicubic maps must be available independently so that the coloring of ascents does not rely on the maps being enumerated.

What would settle it

For n=3 or n=4, count the colored Dyck paths of semilength 9 or 12 and verify whether the total matches the known number of rooted bicubic planar maps on 6 or 8 vertices.

Figures

Figures reproduced from arXiv: 2605.17515 by Jackie N. Kaminski, Juan B. Gil.

Figure 1
Figure 1. Figure 1: Rooted bicubic planar maps on 4 vertices. A bicubic planar map on 2n vertices has 3n edges and n+2 faces. We call a bicubic planar map primitive if it is 3-connected (short for 3-vertex-connected), that is, if the removal of [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Road constructed with back traveling. Once the road is finished, assign to the root edge the label ‘1’ and walk counter-clockwise around the boundary of the created road, starting at the root face. Whenever an edge of the map is reached for the first time (traveling parallel to it or crossing it), increase the labeling by one until all edges have been labeled. This algorithm gives a unique labeling for eac… view at source ↗
Figure 3
Figure 3. Figure 3: Edge-labeled primitive rooted bicubic planar maps on 2, 8, and 12 vertices, together with their corresponding road used for labeling. 1 2 3 4 5 6 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Labeled Dyck path. [2], in this paper we are concerned with the set D g n(3, 0) of Dyck words of semilength 3n created from strings of the form D,U 3D,U 6D,U 9D,U 12D, . . . such that each building block U 3jD may be colored in gj different ways. Equivalently, we could say that each U 3jD, j ≥ 1, may be decorated with any of the gj 3-connected rooted bicubic planar maps on 2j vertices. Notice that, since g… view at source ↗
Figure 5
Figure 5. Figure 5: Gluing operation. The resulting map, denoted by M++ℓ N, is a rooted bicubic planar map with m+n edges whose root vertex is that of M. Lemma 3.1. Let M be a non-primitive rooted bicubic planar map and let e be the first edge that is part of a 2-edge cut set following the road construction from the labeling algorithm. Then M has a 2-edge cut set {e, e′} that decomposes M into two rooted bicubic planar maps M… view at source ↗
Figure 6
Figure 6. Figure 6: Sketch for the proof of Lemma 3.1. If P is a Dyck path of the form U 3nD 3n , decorated by the primitive map B, then we let ϕ(P) = B. Suppose now that P is a Dyck path in D g n(3, 0) of the form U j1D ℓ1 · · ·U jkD ℓk with ji ≥ 1, k > 1, and ascents decorated by primitive maps B1, . . . , Bk with j1, . . . , jk edges, respectively. We then construct a planar map MP = ϕ(P) as follows: ◦ Use the algorithms f… view at source ↗
Figure 7
Figure 7. Figure 7: Decorated Dyck path P. As mentioned in the introduction, we already know that the two sets in question are equinumerous. Thus, it is enough to prove that our map ϕ : P 7→ MP is surjective. We will do that by strong induction in n. Note that the map Θ corresponds to the path U 3D 3 , with ascent decorated by Θ, and the three rooted bicubic planar maps on 4 vertices (shown in [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 8
Figure 8. Figure 8: Construction of M1 = Θ++2 Θ. 2 3 1 4 6 5 M1 8 7 9 Θ 2 3 1 4 6 5 9 8 7 MP [PITH_FULL_IMAGE:figures/full_fig_p007_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Construction of MP = M1++4 Θ. right) to the Dyck paths U 3DU3D 5 , U 3D 2U 3D 4 , and U 3D 3U 3D 3 , with Θ-decorated ascents. In other words, these maps can be written as Θ++1 Θ, Θ++2 Θ, and Θ++3 Θ, respectively. This takes care of the cases n = 1 and n = 2. Suppose now M is a rooted bicubic planar map on 2n vertices with n > 2. If M is primitive, we let PM be the Dyck path U 3nD 3n with M-decorated ascen… view at source ↗
Figure 10
Figure 10. Figure 10: Example of (P ′ 1 ◦b P ′′ 1 ) ◦a P2 = (P ′ 1 ◦a P2) ◦b P ′′ 1 . P = P1 ◦a P2 = (P ′ 1 ◦b P ′′ 1 ) ◦a P2 = (P ′ 1 ◦a P2) ◦b P ′′ 1 (see [PITH_FULL_IMAGE:figures/full_fig_p008_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: A 6-vertex (top) and a 4-vertex (bottom) insertion. In fact, similar insertions may be used to generate all primitives on 14, 16 , and 18 vertices as shown in [PITH_FULL_IMAGE:figures/full_fig_p008_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Generating all primitives on 14 vertices. ∼= ∼= [PITH_FULL_IMAGE:figures/full_fig_p009_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Generating all primitives on 16 vertices. ∼= ∼= [PITH_FULL_IMAGE:figures/full_fig_p009_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Generating all primitives on 18 vertices. illustrated in the above examples. These operations were previously discussed in [5] and referred to as 2-bridging (4-vertex addition) and hexagon addition (6-vertex addition). First, let us formalize the needed insertion operations. Suppose a 3-connected bicubic planar map M on 2n vertices is given. (a) To insert 4 vertices into M, we select a face F and choose t… view at source ↗
Figure 15
Figure 15. Figure 15: a). Here F ′′ stands for the face F with the distinguished edges e and e ′ . (b) To insert 6 vertices into M, we select a vertex v and blow it up by adding a hexagon centered at v. We then connect every other vertex of the hexagon with the three vertices originally adjacent to v and connect the remaining three vertices of the hexagon with vertex v, coloring the added vertices such that the resulting map, … view at source ↗
Figure 16
Figure 16. Figure 16: The 4-vertex insertion and its dual [PITH_FULL_IMAGE:figures/full_fig_p010_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The 6-vertex insertion and its dual. Our second insertion operation leads to the diagram in [PITH_FULL_IMAGE:figures/full_fig_p011_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Subgraphs of M∗ . least one additional vertex E of M∗ that is part of a 3-face incident to one of the edges of that dual subgraph. Thus, without loss of generality, M∗ must contain a subgraph as the one shown in [PITH_FULL_IMAGE:figures/full_fig_p011_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Possible extended subgraphs of M∗ . In case (i), we recognize the dual of a 6-vertex insertion, so removing vertices A, D, F and their incident edges from M∗ will give us the dual of a 3-connected bicubic planar map on 2n − 6 vertices. On the other hand, the subgraph in case (ii) contains the dual of a 4-vertex insertion, so collapsing vertices A, F, C in M∗ into a single vertex will give us the dual of a… view at source ↗
Figure 20
Figure 20. Figure 20: An infinite family of primitives generated by 6-vertex insertions. It is also worth mentioning that some primitive maps can be built with different insertion operations. For example, the map in [PITH_FULL_IMAGE:figures/full_fig_p012_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: A primitive map on 18 vertices. Remark. The statement of Theorem 4.1 appears in [5, Proposition 4] as a consequence of work by Batagelj [3] on 3-connected quadrangulations. The link is somewhat unclear to us, so we chose to include a direct proof here [PITH_FULL_IMAGE:figures/full_fig_p012_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: Truncated octahedral graph Proof. Since the number of rootings of a planar map M with 3n edges equals 6n divided by the number of orientation preserving automorphism on M, the maximal number of rootings occurs precisely when there is only one such automorphism. It was already mentioned that the map M shown in [PITH_FULL_IMAGE:figures/full_fig_p014_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: The primitive map Pˆ. In general, a 4-vertex insertion into a 2m-prism (m ≥ 5) in such a way that the inner 2m-face is subdivided into a (2m − 2)-face, a 4-face, and a 6-face, gives a primitive map on 4m + 4 vertices (n = 2m + 2) with the identity as the only orientation preserving automorphism. With this process, we can generate a family of primitive maps on 2n vertices for n = 12, 14, 16, . . . , having… view at source ↗
Figure 24
Figure 24. Figure 24: All rooted bicubic planar maps on 6 vertices. We finish with a much larger example, n = 14, involving the Dyck path U 18D 6U 3D 8U 18D 4U 3D 24 of semilength 42 (= 3n), with ascents decorated by Θ and two distinct rooted 6-prisms as shown in [PITH_FULL_IMAGE:figures/full_fig_p015_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: Decorated Dyck path Pb. Following the construction given in Section 3, the associated rooted bicubic planar map is the one obtained by the merging operations encoded in Pb [PITH_FULL_IMAGE:figures/full_fig_p016_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: Merging operations encoded in Pb. References [1] J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patterns, Discrete Math. 339 (2016), 1199–1205. [2] D. Birmajer, J. Gil, P. McNamara, and M. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, Lattice Path Combinatorics and Applications, G.E. Andrews, C. Krattenthaler, A. Krinik (Eds.), Springer… view at source ↗
Figure 27
Figure 27. Figure 27: Rooted bicubic planar map MPb corresponding to Pb. [6] M. Noy, C. Requil´e and J. Ru´e, C. R. Math. Acad. Sci. Paris 362 (2024), 143–158. [7] OEIS Foundation Inc. (2025), The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org/. [8] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249–271. Email address: jgil@psu.edu Email address: jnk15@psu.edu Penn Sta… view at source ↗
read the original abstract

We provide a combinatorial proof of Tutte's decomposition of rooted bicubic planar maps into 3-connected components. Motivated by the framework of Bell transformations, we establish an explicit bijection between rooted bicubic planar maps on $2n$ vertices and Dyck paths of semilength $3n$ with ascents of length divisible by 3, where each $3j$-ascent is colored using one of $g_j$ colors corresponding to the rooted 3-connected bicubic maps on $2j$ vertices. Our bijection gives a constructive method for assembling all rooted bicubic planar maps from their 3-connected building blocks. We give a simple proof for the fact that every 3-connected bicubic planar map on $2n$ vertices with $n \geq 4$ can be obtained from a smaller primitive map through just two insertion operations that add either 4 or 6 vertices. Finally, we briefly discuss rootings of 3-connected bicubic maps, providing lower bounds on the minimal number of rootings and showing that prism graphs can be used in combination with our insertion operations to generate maps with the maximum of $6n$ distinct rootings for all $n \geq 11$.

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 / 2 minor

Summary. The manuscript claims to give a combinatorial proof of Tutte's decomposition of rooted bicubic planar maps into 3-connected components. It constructs an explicit bijection between rooted bicubic planar maps on 2n vertices and Dyck paths of semilength 3n whose ascents have lengths divisible by 3, with each 3j-ascent colored by one of g_j colors corresponding to the rooted 3-connected bicubic maps on 2j vertices. The paper also supplies a recursive construction showing that every 3-connected bicubic map on 2n vertices (n≥4) arises from a smaller primitive map by one of two insertion operations adding 4 or 6 vertices, and it gives lower bounds on the number of distinct rootings together with a construction achieving the maximum of 6n rootings for n≥11 using prism graphs.

Significance. If the bijection is established without circularity, the result would supply a constructive combinatorial proof of the decomposition that assembles all maps from their 3-connected blocks, extending the Bell-transformations framework. The explicit two-insertion recursion for the 3-connected case and the concrete bounds on rootings (including the prism-graph construction) are genuine strengths that could support further enumerative work and generating-function derivations.

major comments (2)
  1. [Bijection and coloring step] The central bijection (described after the abstract and in the section introducing the Dyck-path encoding) colors each 3j-ascent with one of g_j colors, where g_j counts rooted 3-connected bicubic maps on 2j vertices. The manuscript must explicitly demonstrate that the recursion for these g_j (via the two insertion operations adding 4 or 6 vertices) is derived and solved independently of the full Dyck-path decomposition; otherwise the argument that the bijection proves Tutte's decomposition becomes circular.
  2. [Recursive construction for 3-connected maps] Section on the recursive construction for 3-connected maps: the claim that every 3-connected bicubic map on 2n vertices (n≥4) is obtained from a smaller primitive map by exactly two insertion operations is load-bearing for the independence of g_j. The base cases (n=4 and the primitive maps) and the verification that this recursion does not presuppose the global Dyck-path bijection need to be stated with explicit small-n checks.
minor comments (2)
  1. [Abstract] The abstract refers to 'Bell transformations' without a one-sentence reminder or citation; a brief parenthetical gloss would help readers outside the immediate subfield.
  2. [Bijection definition] Notation for ascent blocks and the coloring function could be illustrated with a small explicit example (e.g., n=4 or n=5) to make the bijection easier to follow on first reading.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for highlighting the importance of establishing the independence of the recursive enumeration from the Dyck-path bijection. We address each major comment below and will incorporate clarifications and explicit verifications in a revised version.

read point-by-point responses

  1. Referee: [Bijection and coloring step] The central bijection (described after the abstract and in the section introducing the Dyck-path encoding) colors each 3j-ascent with one of g_j colors, where g_j counts rooted 3-connected bicubic maps on 2j vertices. The manuscript must explicitly demonstrate that the recursion for these g_j (via the two insertion operations adding 4 or 6 vertices) is derived and solved independently of the full Dyck-path decomposition; otherwise the argument that the bijection proves Tutte's decomposition becomes circular.

    Authors: The recursive construction and the resulting enumeration of g_j are developed entirely within the section on 3-connected maps, using only direct combinatorial arguments on the maps themselves: every 3-connected bicubic map on 2n vertices (n≥4) is shown to arise from a unique smaller primitive map by one of the two specified insertions. This decomposition is proved by case analysis on the structure of the map (e.g., location of the root edge and the faces incident to it) without any reference to Dyck paths or the global bijection. The numbers g_j are therefore obtained as the solution to this self-contained recurrence with explicit base cases. The bijection is introduced only afterward and simply uses these independently computed g_j as the palette of colors for the 3j-ascents. We will add a short clarifying paragraph at the beginning of the bijection section that explicitly states the logical order and independence of the two parts. revision: yes

  2. Referee: [Recursive construction for 3-connected maps] Section on the recursive construction for 3-connected maps: the claim that every 3-connected bicubic map on 2n vertices (n≥4) is obtained from a smaller primitive map by exactly two insertion operations is load-bearing for the independence of g_j. The base cases (n=4 and the primitive maps) and the verification that this recursion does not presuppose the global Dyck-path bijection need to be stated with explicit small-n checks.

    Authors: We agree that explicit small-n verification will make the independence transparent. In the revised manuscript we will insert a new subsection (or short appendix) that lists all rooted 3-connected bicubic maps for n=4,5,6,7 together with the unique predecessor map and the insertion type used in each case. For n=4 the single primitive map is exhibited directly; for n=5 and n=6 we enumerate the maps obtained by each insertion and confirm that the resulting collection is exhaustive and matches the known small values of g_n. These checks are performed by hand on the maps and make no use of the Dyck-path encoding, thereby confirming that the recursion stands on its own. revision: yes

Circularity Check

0 steps flagged

No significant circularity: independent recursion for 3-connected blocks

full rationale

The paper supplies an explicit bijection that assembles full rooted bicubic maps from 3-connected blocks whose counts g_j are obtained via a separate, self-contained recursive construction (two insertion operations adding 4 or 6 vertices, proved directly for n≥4). This recursion is presented as an independent fact about primitive 3-connected maps and is not derived by restricting the Dyck-path decomposition being proved. The bijection therefore uses g_j as externally supplied combinatorial data rather than re-deriving it from the same mapping. No self-definitional loop, fitted prediction, or load-bearing self-citation appears in the given derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard facts from planar graph theory (Euler's formula, 3-connectedness) and the known existence of Tutte's decomposition; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Every rooted bicubic planar map admits a unique decomposition into 3-connected components along cut vertices or edges.
    This is the statement whose combinatorial proof is supplied; it is invoked as the target of the bijection.

pith-pipeline@v0.9.0 · 5743 in / 1414 out tokens · 48585 ms · 2026-05-19T22:31:26.474105+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]

    Baril, R

    J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patterns, Discrete Math.339(2016), 1199–1205

    work page 2016

  2. [2]

    Birmajer, J

    D. Birmajer, J. Gil, P. McNamara, and M. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials,Lattice Path Combinatorics and Applications, G.E. Andrews, C. Krattenthaler, A. Krinik (Eds.), Springer, 2019, 155–165

    work page 2019

  3. [3]

    Batagelj, An inductive definition of the class of 3-connected quadrangulations of the plane,Discrete Math.78(1989), 45–53

    V. Batagelj, An inductive definition of the class of 3-connected quadrangulations of the plane,Discrete Math.78(1989), 45–53

    work page 1989

  4. [4]

    Birmajer, J

    D. Birmajer, J. Gil, and M. Weiner, A family of Bell transformations,Discrete Math.342(2019), 38–54

    work page 2019

  5. [5]

    Horev, M

    E. Horev, M. J. Katz, R. Krakovski, A. Nakamoto, Polychromatic 4-coloring of cubic bipartite plane graphs,Discrete Math.312(2012), 715–719. ROOTED BICUBIC PLANAR MAPS VIA DYCK PATHS 17 Figure 27.Rooted bicubic planar mapM bP corresponding to bP

    work page 2012

  6. [6]

    M. Noy, C. Requil´ e and J. Ru´ e,C. R. Math. Acad. Sci. Paris362(2024), 143–158

    work page 2024

  7. [7]

    (2025), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org/

    OEIS Foundation Inc. (2025), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org/

    work page 2025

  8. [8]

    W. T. Tutte, A census of planar maps,Canad. J. Math.15(1963), 249–271. Email address:jgil@psu.edu Email address:jnk15@psu.edu Penn State Altoona, 3000 Ivyside Park, Altoona, PA 16601

    work page 1963