ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 51-71
https://doi.org/10.26493/1855-3974.1615.979
(Also available at http://amc-journal.eu)
4-edge-connected 4-regular maps on the projective plane*
*
Shude Long
Chongqing Key Laboratory of Group & Graph Theories and Applications, Chongqing University of Arts and Sciences, Chongqing 402160, P. R. China
Han Ren t
Department of Mathematics, Shanghai Key Laboratory ofPMMP, East China Normal University, Shanghai 200241, P. R. China
Received 21 February 2018, accepted 14 November 2019, published online 13 June 2020
In this paper rooted (near-)4-regular maps on the projective plane are investigated with respect to the root-valency, the number of edges, the number of inner faces, the number of nonroot-vertex-loops and the number of separating cycles. In particular, 4-edge connected 4-regular maps (which are related to the 3-flow conjecture by Tutte) are handled. Formulae of several types of rooted 4-edge-connected 4-regular maps on the projective plane are presented. Several known results on the number of 4-regular maps on the projective plane are also derived. Finally, using Darboux's method, a nice asymptotic formula for the numbers of this type of maps is given which implies that almost every (loopless) 4-regular map on the projective plane has a separating cycle.
Keywords: (Rooted) near-4-regular map, separating cycle, Lagrangian inversion, enumerating function, asymptotic.
Math. Subj. Class. (2020): 05C10, 05C30, 05C45
* The computations of the approximate resultants were carried out with the aid of a symbolic algebra system (Maple [32]) on a Pentium II. The authors are grateful to the referees for their careful reading of this paper. Their constructive suggestion enabled us to make some major revisions which made this paper more readable and concrete. Supported by the the NNSFC under Grant No. 11171114, Science and Technology Commission of Shanghai Municipality (STCSM) under Grant No. 13dz2260400 and the Natural Science Foundation Project of CQ under Grant No. cstc2019jcyj-msxmX0724. t Corresponding author.
E-mail addresses: longshude@163.com (Shude Long), hren@math.ecnu.edu.cn (Han Ren)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
34
Ars Math. Contemp. 18 (2020) 51-49
1 Introduction
Graphs here are connected with loops or multi-edges permitted. Terms mentioned without definition may be found in [8, 28, 48]. A graph (map) is k-(edge-)connected if it takes the removal of at least k (edges) vertices to separate the graph (map) [8]. Notice that a 2-connected graph (map) may have loops which have been excluded by Tutte [44]. A pair of edges {e1,e2} is called a 2-edge-cut if removing of them will result in a disconnected graph (map). A cycle is separating if removing its edges will leave a disconnected graph (map). It is clear that in a 4-regular graph (map) on the projective plane any 2-edge-cut is contained in a separating cycle.
A planar map (projective planar map) is a graph G drawn on the sphere S0 (the projective plane N1) such that no two edges cross and each component of S0 - G (N1 - G) is homeomorphic to an open disc called a face whose boundary is the facial walk. In the same way, we may define a map on higher surfaces. A circuit C on a surface E is essential (or noncontractible as some people named it) if E - C has no component which is homeomorphic to an open disc. Otherwise it is called planar (or trivial).
A map is rooted if an edge, a vertex incident to the edge together with a direction along one side of the edge are all distinguished. The essence of rooting a map is to trivialize the automorphism group and set up equation(s) of the enumerating functions which makes it possible to determine the solution in an algebraical or analytic way. Furthermore, many results on rooted maps are valid for unrooted maps in terms of asymptotic evaluation since there are at most 4n ways to root an n-edged map. There has been a trend to evaluate the distributions of a certain type of maps in random map theory [6, 16, 18, 41]. Following the path of Tutte [46] and Brown [9], people have investigated many quadratic equations (or equations much related to them) and got much information about the number of maps. Although some pioneers such as Walsh et al. [50, 51], D. Arques [1], E. A. Bender et al. [4, 5] and Gao et al. [17] did some influential works on nonplanar maps in an exact way, elegant formulae are very difficult to obtain for maps on higher surfaces. People such as E. A. Bender et al. started systematically working on asymptotic evaluations of rooted maps. Many scholars such as E. A. Bender et al. [3], G. Chapuy et al. [12], Gao [14, 15], A. Mednykh et al. [33, 34] and T. R. S. Walsh et al. [49] have investigated many types of maps on general surfaces and gotten asymptotic evaluations of nonplanar maps up to now. For a survey one may see [7] or [25].
4-regular maps are very important for their applications in many fields such as rectilinear embedding in VLSI, the Gaussian crossing problem in graph theory, the knot problem in topology and the enumerations of some other types of maps [26, 27, 28, 29]. For instance, Bender et al. showed [6] that there exists a close relation between the face-width (a concept due to Hutchinson [21]) and the edge-width of a graph on a surface through an extended bijection of Brown [10] between n-edged maps and n-faced bipartite quadrangu-lations; a result of Tutte [43], every 2k-edge-connected graph has k edge-disjoint spanning trees, together with a formula of Xuong [52] shows that a 4-edge-connected graph is up-embeddable (i.e., may be embedded into an orientable surface with at most two faces). Let k > 1 be an integer and G = (V, E) a multigraph. A Z-flow f on G such that 0 < |f (e )| < k for all e G E is called a k-flow. Tutte's 3-flow conjecture [42], which is still open, states that every 4-edge-connected 4-regular graph has a nowhere-zero 3-flow. Although Grotzsch [20] showed its validity for planar graphs, Tutte conjectured that this statement should still be valid without the requirement that the graph be planar. Jaeger
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	53
proved [22] that every 4-edge-connected graph has a nowhere-zero 4-flow. However, the difficulty to give a positive answer for the existence of a nowhere-zero 3-flow shows that there is still a long way to go. Instead, Jaeger raised the weak 3-flow conjecture: There is a fixed integer k such that every k-edge-connected graph has a nowhere-zero 3-flow.
A (rooted) near-4-regular map is a map having all the vertices 4-valent except possibly the rooted one. A map is called Eulerian if all the valencies of its vertices are even. It is clear that a near-4-regular map is Eulerian and 2-edge-connected. Rooted (near-)4-regular maps (or their duals: quadrangulations) have been investigated by many scholars. We list them (as far as we know) as follows (among which some are not 4-regular):
(1)	rooted bicubic maps [46];
(2)	rooted trees [45];
(3)	rooted quadrangulations [10];
(4)	rooted c-nets via quadrangulations [35];
(5)	rooted one-faced maps on surfaces [ , pp. 212-213];
(6)	rooted 4-regular planar maps [ , pp. 159-166];
(7)	rooted near-4-regular planar Eulerian trials [38];
(8)	rooted loopless 4-regular maps on the projective plane, the torus and the Klein bottle [36, 39, 38, 37];
(9)	rooted 2-connected 4-regular maps on the plane and the projective plane [30, 40];
(10) rooted 4-edge-connected 4-regular maps on the plane [31].
We expect that several more classes of 4-regular maps could be added into this list. In fact, Z. C. Gao showed us his interest in enumeration of simple Eulerian maps through the conversations at 2000's Workshop of Graph Theory with Applications at Nanjing Normal University. As an approach to this open problem, we investigate the number of rooted 4-edge-connected 4-regular maps on the projective plane and give a formula, through which an exact formula may be derived, for this type of maps. Furthermore, by using the Dar-boux's method, we present a nice asymptotic formula for them. Although we did some work on this as shown in the list, the main result(s) of this paper is much closer to the answer since a 4-edged-connected 4-regular map is 2-connected without loops and there are at most two multi-edges between a pair of vertices and there are infinitely many 2-connected 4-regular maps with three multi-edges connecting two vertices. Finally, as an application of those facts, we conclude that among rooted 4-regular maps on the sphere (or the projective plane) almost all of such maps have at least one separating cycle.
Remark 1.1.
(1)	Since Tutte's 3-flow conjecture is still open for general graphs, our results may be viewed as an approach to it.
(2)	Here we regard planar trees or generally maps with one face on surfaces, which some people also called monopoles, as a special kind of near-4-regular maps.
34
Ars Math. Contemp. 18 (2020) 54-49
2 Maps on the projective plane
In this section we shall set up a general equation with up to five more parameters for rooted near-4-regular maps on the projective plane. We first give some definitions on maps.
Let U and Up, respectively, denote the set of the rooted near-4-regular maps on the plane and the projective plane. Let their enumerating functions be, respectively, as
f(x,y,z,t,w) = £ x2m(MV(M)zn(M)ta(M^(M>,
m eu
fp(x,y,z,t,w) = £ x2m(MV(M^n(M)ta(M^(M\ m eup
where the variables x, y, z, t and w mark, respectively, the root-valency, the number of edges, the number of inner faces, the number of nonroot-vertex-loops and the number of separating cycles of M. The set Up may be partitioned into three parts as
Up = Up1 + Up2 + Up3,
where
Up1 = {M | er (M) is a planar loop}, Up2 = {M | er(M) is an essential loop}, Up3 = {M | er (M) is a link},
in which er (M) is the rooted edge of M; when er (M) is not a loop, it is called a link.
Lemma 2.1. Let U(p1) = {M - er (M) | M G Upi}. Then
U(pi) = U © Up + Up © U,
where "©" is the Iv-addition of the sets of maps defined in [28, pp. 88-89].
Here the operation © of two maps is defined as follows: For two maps M1 and M2 with their respective roots r1 = r(M1) and r2 = r(M2), the map
M = M1 U M2
with M1 n M2 = {v} such that
v = vri = vr2
is defined such that its root, root-vertex and root-edge are as the same as those of M1 but the root-face is the composition of fr (M1) and fr (M2). The operation for getting M from M1 and M2 is called the Iv-addition and the map is written as
M = M1 © M2.
Further, for two sets of rooted maps M1 and M2 , the set of maps
M1 ©M2 = {M1 © M2 | M1 G M1, M2 G M2}
is said to be the Iv-production of M1 and M2. If M1 = M 2 = M, then we are allowed to write
M © M = M®2,
and further,
M®k = MG(fc-1) ©M.
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	55
Proof. For a map M e Up, the root-edge er (M) is a planar loop. The inner and outer regions determined by er (M) are, respectively, two elements of U and Up. Since this procedure is reversible, the lemma follows.	□
By the above lemma and the reasoning used in [36, Lemma 3.1] the enumerating functions of Up1 and Up2 are, respectively,
fpi = 2x2yzffp	(2.1)
and
f 2 d (xf) ~
fp2 = x y dx .	(2.2)
The following result is easy to obtain from the definition.
Lemma 2.2. Let U(p3) = {M • er (M) | M e Ups}. Then U(p3) = Up -Up(2), where Up(2) is the set of maps in Up whose root-valencies are all 2.
Here, M^er (M) is the map obtained by contracting (or shrinking) the root-edge er (M) of M into a vertex (i.e., identifying the two ends of er (M) along it). The reverse operation is the so-called splitting the root-vertex. It is clear that splitting the root-vertex of a near-4-regular map M may create at most one near-4-regular map. By Lemma 2.2, the enumerating function of U(p3) is
f(p3) = fp - x 2Fp(2),	(2.3)
where Fp (2) is the enumerating function of Up(2).
If the splitting operation results in a nonroot-vertex loop, the root-edge of the resultant map is contained in a 2-edge-cut. Since splitting the root-vertex may create nonroot-vertex loops, among which some are planar ones while others are essential, the set U(p3) has to be divided into several more parts as U(p3) = J2i=1 U(p3), where maps in U(®p3) (1 < i < 5) have the structures as depicted in Figure 1 (which defines several types of possibilities of a nonroot-vertex loop after splitting the root-vertex).
Remark 2.3.
(1)	Maps of type 1 (or 2) have their edge er (M) (or ePr (M)) the planar loop. Here P is the permutation of the edges of M incident to the root-vertex.
(2)	Maps of the above types may create new separating cycles after splitting the root-vertex.
In order to set up recursive relations of maps, we should first state some basic facts for embeddings of graphs on surfaces.
Fact 2.4. Let G(M) be a 2-edge-connectedgraph (map) with {e1, e2} a 2-edge-cut. Then e1 and e2 are on the same separating cycle (which is a part of facial walk of M).
Proof. One may verify this from the fact that for a 2-edge-cut as defined above, each cycle passing through e1 will also contain e2 and each facial walk containing e1 will also has a shortest simple subwalk passing through e1 and e2.	□
34
Ars Math. Contemp. 18 (2020) 56-49

(a) M gU^
(b) M G^
(c) M GW^
(d)M eW(;3)
(e) M GW(5p3)
Figure 1: Five types of maps which will induce a nonroot-vertex loop after splitting the root-vertex.
Fact 2.5. Let M be a map as defined in Figure 1. Then after splitting the root-vertex, the root-edge of the resulting map will be on a separating cycle.
Proof. This may be concluded from the definition of the vertex-splitting procedure. □
An edge in a map is called singular if it lies on the boundary of exactly one face. Otherwise, it is nonsingular. The following fact shows that a projective planar map with a singular edge is determined by performing an edge-twisting operation on an edge in planar maps.
Here the so-called edge-twisting operation is defined to replace an edge e with a Mobius strip.
Fact 2.6. Removing of a singular edge on a cycle in a projective planar map will result in a planar map. Conversely, by twisting a nonsingular edge e in a planar map will re-embed its underlying graph into the projective plane.
Since splitting the root-vertex may lead to a new nonroot-vertex loop or separating cycle, there are several more cases which must be handled.
Case 1. The maps of W(p3).
Notice that for a map of W(p3), one thing will happen: both the number of nonroot-vertex loops and the number of separating cycles will increase after splitting the root-vertex. Let ei = eP2r, where P is the permutation of the edges incident to the root-vertex. Then the set Wl„3) can be partitioned into two parts as
U(U) = "¿3) + "¿I),
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	57
where
U(p3) = {M | e1 is contained in a 2-edge-cut}, U(p23) = {M | ei is not contained in any 2-edge-cut}.
Hence, by Facts 2.4 and 2.5, a map M in U^) will have a 2-edge-cut containing ei together with another edge, say e2. Let e2 be chosen such that size of the component of M - {e1, e2} containing the root-vertex will be as small as possible which is as shown in the left side of Figure 2, where the shaded region is either a planar map or a nonplanar map and f represents the possible (inner) face containing e1 and e2. Notice that f may be identical to the root-face which will happen only in the case of e2 being singular.

Mi M2
Figure 2: One type of maps containing a 2-edge-cut {e1, e2}.
In general, people use df to denote the boundary of a face f. Here we use this to denote the shortest closed subwalk of f which contains the 2-edge-cut {e1, e2}. One may see that those two concepts coincide in the planar case.
Subcase 1.1. e2 is a singular edge.
By Fact 2.6 and the discussion used in the planar case in [31], the contribution of such type of maps to Up is
x2y(F(2) - yz),
^^ F(2) (f - !),	(2.4)
where F(2) is the enumerating function of those maps in U whose root-valency are all 2.
In fact, in this situation the shortest closed subwalk of df in a map M (as shown in the left part of Figure 2) containing {e1, e2} is an essential cycle and the operation in Figure 2 results in two planar maps M1 and M2 where M1 G U(2) - L, the set of non-loop maps in U whose root-valencies are all 2 while M2 is a map which is the lv-addition of a loop map and a planar one. We denote the enumerating functions of the above three types of maps M, M1 and M2 are, respectively, P, Q, R. It is clear that the reverse operation from M1 and M2 to M in Figure 2 does not increase the number of inner faces, nonroot-vertex loops and separating cycles. Therefore, P = F( R. Since R = xFy2)Z (f - 1), we have (2.4).
Subcase 1.2. e2 is a nonsingular edge.
In this case, removing the edge e2 from M will leave a projective planar map, i.e., M - e2 is a map on N1 with e1 a bridge (i.e., a separating singular edge) connecting two types of maps M1 and M2 as shown in the right side of Figure 2.
34
Ars Math. Contemp. 18 (2020) 58-49
Subcase 1.2.1. M1 is nonplanar and M2 is planar.
Now M corresponds to two types of maps. One is in Up (2), a subset of Up containing the maps with their root-valencies being 2 while the other is a planar one with the edge eP2r (= e1) which is not on any separating cycle. This correspondence has been depicted in Figure 3.

A map in Up (2) Figure 3: Decomposition of a map into two types of maps.
Let Up(2) be the set of those maps in Up such that their root-valencies are all 2. Since rooted edges of maps in Up (2) are all nonsingular, its contribution to Up is
Fp(2) = Fp(2) - 1F(2),
where Fp(2) and F(2) are, respectively, the enumerating functions of Up(2) and U(2) (which is the set of maps in U such that their root-valencies are all 2). As we have reasoned in the proof of (2.4), this combined with (2.4), implies that the total contribution of the maps in this subcase is
Fp(2) - 1F(2) x2y2z2(f - 1)
yz
F(2)
(2.5)
Subcase 1.2.2. M1 is planar and M2 is nonplanar.
This time we have a similar situation as we got in Subcase 1.2.1, i.e., maps in this case may be decomposed into two types of maps such that the map in rightmost part of Figure 3 is a nonplanar map. Notice that a map of the type in the rightmost side of Figure 3 is in Upg) such that its edge eP2r is nonsingular. We denote the set of such type of maps as UPi). Then
U(p3)
7/121 , 7/122
U(p3) + U(p3),
where U^2) is the subset of U^ whose maps have their edge ep2r being singular. Also by the same reason as above, the enumerating function of Up2^ is
1 x2y2z2(f - 1)
z F (2) ■
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	59
Thus, we have the contribution of the maps in this case as
F(2) - yz ( 12 x2y2z2(/ - 1) \
/(p3) F(2 ) '	(2'6)
where /¿p23) is the enumerating function of W^). By (2.4), (2.5) and (2.6) and the fact /¿>3) = x2yz/p, we see that the total contributions of the maps in those cases satisfy
x2yz/p = x2y(Fj2)- yz) (/ - 1) + x2yZ(FP(l)~ 1F (2)) (/ - 1)
F (2)	'	F (2)
2) - yz f 12 _ x yz V(p3) " F (2)
+ F(2) - yz ( 12 x2y2z2(f - 1)\ f 12
+ yz f(p3) FT2 + fp3)-
After simplification we find that
_ xW f Fp(2) - 1F(2) ( 1 f(p3) _ f(2) f	F(2) f	■
Since
fi - yt /11 ytw/12
fp3 - x2 f(p3) + x2 f(p3),
where fp3 is the enumerating function of Wp3, we have that
fi = f y3zt(w - 1) „1 f y3zt(w - 1)(FP(2) - 1F(2)) (f 1)
f3 - \ F(2) +y	F„(2)	(f - 1)-
Hence,
y ,1 _ i y3zt(w - 1)
- X2 /¿.S) _{+y2(t -1)} f
(2) — 1 F (2))
f - 1).
(2 7)
y3zt(w - 1)(Fp(2) - 1F (2)),	^
F 2 (2)
Case 2. The maps of U(p3).
Since maps in this case have a very similar structure as those in Case 1 except for the ways of putting the planar loop eP2r, so we have
/'p3 - X2 /(p3) = /p3 - Xy /(p3).	(2.8)
Case 3. The maps of U3p3).
Since the set of maps of this type satisfies
Wp3 = Lp © Wp;
where Lp is the loop map on N1, the projective plane. By the result obtained in [31] (or a similar procedure as the proof of (2.4)) we conclude that
/p3 - X2 /(p3) = ^F^-1) (/ - 1) + y2(t -1)(/ -1).	(2.9)
34
Ars Math. Contemp. 18 (2020) 60-49
By rearranging the root-edges of those in U(3p3) which are singular we get all of those in U3p3) + U(p3). After an analogous procedure as we did in Case 3 we obtain
fp3 - J2f(p3) = fp3 - f(p3) = fp3 - f(p3),	(2.10)
where /3 (/(p3)) is the enumerating function of U*3 (U(®p3)), 1 < i < 6.
Case 4. The maps of U(6p3).
Since splitting the root-vertex of a map of this type will not create a nonroot-vertex loop but may result in a 2-edge-cut containing the root-edge, we have to partition the set U(6p3) into several more parts as
6
U(p3) =J2 UCp3)>
i=1
where maps in U(6p3) (1 < i < 5) have the structure shown in Figure 4 where splitting the root-vertex will lead to a 2-edge-cut containing their root-edges.
(a) M G^
(b) M GU(6p3)
(c) M GU(6p33)
(d) M G U(6p43)
(e) M GU(6p53)
Figure 4: Maps which are composed of U — L (or Up (2) - Lp) and a subset of Up (or U).
Here we use L and Lp to denote, respectively, the loop-map on the sphere and the
projective plane. Further, we use fp3 (/6p3)) to denote the enumerating function of Wp3
(U(p3))' 1 < i < 6.
One may see that the structures for maps M in W^3) and W(®63) (1 < i < 6) are the same except for whether a new nonroot-vertex loop appears or not after splitting the root-vertex of M. Therefore,
f6! = x2yz(F(2) - yz) ( Fp(2) - 1F(2)(/ 1)
f(p3) —	^^	1 fP--cVo\	(/ - 1)
F(2)
F(2)
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	61
and further
f 61 _ Af61 _ y2z(w - 1)(F (2) - yz)
fp3 x2 f(p3)	F (2)
fp -
Fp(2) - 1F(2) F (2)
(f - 1)
(2.11)
Since correspondences like this exist between Uf and Up3 for 2 < i < 5, repeating similar procedures we may establish that
f62_if62 _ y2z(w - 1)(F(2) -yz)
fp3 „2 f (p3) _
fp3 - X2 f(p3) _
F(2)
fp -
Fp(2) - 1F(2) F (2)
(f - 1)
y r6¿ _ y2(w - 1)(F(2) - yz)
(2.12)
F(2)
(f - 1), 3 < i < 5.
We now begin to handle the maps in Upf. By the definition, a map in Upf is not separable at the root-vertex. Given that the possibility of creating new separating cycles, the set U®f has to be further partitioned into two parts as
U636
661 662 : Up3 + Up3 >
where splitting the root-vertex of the maps in Upf1 will create a new separating cycle with a structure shown in the left side of Figure 5.
A 4-regular map
Figure 5: A map in U^ with an unique edge e lying on a new separating cycle after splitting the root-vertex and may be decomposed into two types of maps.
Let M be a map in U®f1. Then it is not separable at the root-vertex and contains an unique edge, say e, such that removal of e will make it separable at the root-vertex. Further, M - e = M1 © M2 and the root-valency of M1 is 3. Since M1 and M2 may be of distinct types of maps, there are several cases that must be handled.
Subcase 4.1. e is singular
By Fact 2.6 this is in fact a planar case we have handled in [31] and maps of this type contribute
x2F (4) zF (2)
(f - 1)
(2.13)
to Up, where F(4) is the enumerating function of those 4-regular maps in U which are not separable at the root-vertex.
Subcase 4.2. e is nonsingular.
34
Ars Math. Contemp. 18 (2020) 62-49
For a map M of this case, M - e = M1 © M2 and there is only one nonplanar map among M1 and M2. Notice that this will not hold in the general case for the maps which are composed this way. But this possibility has been excluded now. Thus, two subcases will be introduced.
Subcase 4.2.1. Mi is nonplanar and M2 is planar.
As we have reasoned in the Subcase 1.2.1 of the maps in U(p3), M may be decomposed into two maps as shown in Figure 5. This determined by M1 is a 4-regular map in Up(4) such that the edge eP-ir is nonsingular. Further, we let Up (4) be the set of those maps. On the other hand, the one determined by M2 is a planar map having its root-edge outside of any separating cycle. Through a very similar procedure as we used in the Subcase 1.2.1 of the maps in U(p3) we see that the contribution of this case to Up is
x2Fi(4) F (2)
(f - 1),
where Fp (4) is the enumerating function of Up (4). By subtracting the contribution of those determined by the maps in U(4) we conclude that the enumerating function for maps of this case is
x2(F„(4) - ZF(4)) N ( P(j)(2)z ( )) (f - 1),	(2.14)
where Fp(4) counts the maps in Up(4). Subcase 4.2.2. Mi is planar and M2 is nonplanar.
Similar to what we have analyzed in the corresponding situation of the maps in U(p3), maps of this case may be decomposed into two types of maps, among which one is determined by twisting the edge which is one edge ahead of the root-edge along the root-face of a map in U(4) and the other is in U(6p632) whose root-edge is nonsingular. By repeating an analogous but much more complicated manipulation we find that the enumerating function for maps of this type is
x2FP(4) f _ Fp(2) - iF(2) - 1 (f - 1)
F(2) \JP	F(2)	z
Combining all the three cases shows that the enumerating function of U^ is
2F(4).,	x2(Fp(4) - iF(4))
f661 = x F (4) (f 1) + x (Fp(4) - ZF (4)) (f 1) f63) = ~ZF(2) (f - 1) +	F(2) (f - 1)
+ XlMif _fp(2)-1F(2) 1(f 1)
+ F (2) \fp	F (2)	z(f 1)
This implies that
fp3 - X2 f(663) = Fp(4)(f -1)
+f i Mi fp - Fp(2F2F(2) - iff - '>* <215>
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	63
Now we are in a position to obtain our first main result. Equations (2.1) - (2.15) yield
fp = 2x2yzffp +	+ J2 Up - x2Fp(2)}
5	5
, V^ ( fi y fi \ , ( r6i y r6i \ , r661 y r661 + ¿^ fp3 - J2 f(p3)J + Z^ fp3 - J2 f(p3)J + fp3 - J2 f(p3)
i=1 i=1
2x2yzffp + J2y^J + {/p - J2Fp(2)} + 2 {y2(t - 1)} fp - 2y3zt(w -	- 1F(2)) (f - 1)
+3 (f - i)+3y2(t -1)(/ -1)
>y2z(w - 1)(F(2) - yz) {, Fp(2) - 1F(2)
+ 2	F (2)	\fp	F (2) (f 1)
, 3y2(w - 1)(F(2) - yz) (
+ 3 F(2) (/ -1)
+ Fp(4)(f - 1) + F 1<4) fp -	- 1
By considering the coefficient of fp we have that
J2 - y - 2x4yzf -	+ y^ - 1)
2x2y2z(w - 1)(F(2) - yz) x2y(w - 1)F(4) _

—(2) —(2)
where A is the discriminant of the following quadratic equation for planar maps obtained in [31]:
x4yz/2 + (y - x2G)/ + x2G - y - x2y—(2) = 0, 2y3z2t(w - 1) 2 ,
G =1 - y -) - 2y2z(i - 1)	(2.16)
2 .	(2) - yz	_ —(4)
- y2z(w -1) - y(w -1) ^ .
Theorem A. The enumerating functions /p and / satisfy the following equation:
rr 4 dxf 2 , , x2y3zt(w - 1)(—„(2) - 1 -(2)), s -V^/p = ^y^f - x2y—p(2) - 2-j)2(2)( ) z ()) (/ - 1)
+ 3X2y3—t((2 - 1) (/ - 1) + 3y2(t - 1)(/ - 1) + 3x2y2(t - 1)(/ - 1)
_2x2y2z(w - 1)(—(2) - yz) ( —p(2) - 1—(2) ( 1) 2 —(2) 1 —(2) (/ 1)
, 3x2y2(w - 1)(—(2) - yz)(/ 1) + 3 —^ (/ - 1)
Fp(4)(/ - 1) - ^(Fp(2) - 1F(2)) - ^
34
Ars Math. Contemp. 18 (2020) 64-49
Remark 2.7. Since the above equation contains 5 or more parameters and much information, many known results such as for monopoles on N [36], 4-regular maps on N [36] (the case of t = w = 1) and loopless 4-regular maps on N1 [ ] (the case of t = 0, w = 1) may be derived. If more parameters are introduced, more results will be obtained. But here we are only interested in the case of 4-edge-connected 4-regular maps on N since they are more closer to the simple Eulerian maps which is what we shall handle in the next section.
3 Calculations
In this section we shall concentrate on the calculation of the function in Theorem A and all the arguments are under the restriction t = w = 0, y = 1 since this is what we are really interested in and may be handled by the double-root method developed by Brown [11]. Since t = w = 0 will destroy all the nonroot-vertex loops and all the separating cycles, we have that F(2) = z, Fp(2) = 1. Now the equation in Theorem A becomes
= {- 1 - 3(/ - 1) - m-u - 1) +	-1)}
where
-V7^ = Hx2 - 1 - 2x4zf, H = 1 + 2z + ^.	(3.1)
F (2)
Let x2 = n denote a double root of A. Then after simplifications we obtain
Theorem B. The enumerating function of rooted 4-edge-connected 4-regular maps on the projective plane is
. _ 1 -n/t-4/ + _L/ _ 3z + FZ4),
1 - / \	zn	/1 - /	z
where
2 3
z2n
fn(2 - f ) = 1, n = 1 + 1 - 4n 2.	(3.2)
Remark 3.1. By applying Lagrangian inversion (for a reference one may see [19]) for (3.2) and its other version
z2
t = 1 + 4ZZ-72' tn = 1,
we may expand Fp(4) into a power series of z, i.e.,
Fp(4) = £ z(n + 1)fm+1 - £ -C2m -12) zmn2m-1f- 4z - 1 + 2znf +1,
m> 0	m>1 v	'
~	n>0
where
s (2k- s - 1
fs = V^ s	2k - s - 1 tk
f Z^ k22fc-n k- 1 I
k>s
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	65
4ns /m + n - 1\ (m-1)
m- 1 yDn=1 (n	)z >
ts =
Z	\ 4 S
1 — 4Z	m!
m>1
n>0
4z — 1 + ^ 4m+nm! I m - 1 I ^i=1
>1
>0
m + n ^ d(™-1) (+2n+s-1\_m-n
)(t2n+s-1)z
Here
Dm/(x) =
dm/ (x)
dx™
By using an algebraic symbolic system such as Maple [32], the first few coefficients of Fp(4) may be calculated:
Fp(4) = 6z2 + 21z3 + 94z4 + 471z5 + 2516z6 + 14006z7 + 80246z8 + 469635z9 + 2793758z10 + 16835979Z11 + 102530832z12 + 629875252z13 + 3898000312z14 + 24274540180z15 + 151988898790z16 + 956148311939z17 + 6040124414714z18 + •• •
One may compare the initial values of the maps with the number presented by the formula above and see that they coincide with each other. For instance, there are 6 rooted 4-edge-connected 4-regular maps with 3 faces on N1 and the following group of unrooted maps (as shown in Figure 6) will induce 21 distinct rooted maps with 4 faces on N1.
(a) M1
(b) M2
(c) M3
(d) M4
Figure 6: Four distinct embeddings of the double graph on N1 which will induce 21 rooted maps.
The contributions of the 4 maps to the rooted maps are, respectively, listed in Table 1.
s
n
x=a
106	Ars Math. Contemp. 18 (2020) 105-115
Table 1: Initial values for 3-vertex rooted maps on N1.
M1 | M2 | M3 | M4
12 I 6 I 2 I 1
4 Asymptotic evaluations
In this section we concentrate on the approximate values of the number of the maps obtained in the previous section. We first state some basic facts.
Fact 4.1. Let M be a class of infinite rooted maps with M1 as its subset. Suppose that their enumerating functions may be expanded into power series and their respective convergence radiuses are R and R1. Then R and R1 are, respectively, the singularities of them. Furthermore, R < R1.
Fact 4.2 (Long [30]). The convergence radius of the power series expansion with the number of inner faces as the parameter of the enumerating function for the rooted 2-connected 4-regular maps without loops on the projective plane is 17. Consequently, rooted 4-edge-connected 4-regular maps on the projective plane must have its convergence radius, say r, of enumerating function satisfying 17 < r < 1.
As we have reasoned in [ ], the function H = G|y=1 (defined in Theorem A) and the parameter n = x2 = x may be rewritten as
23
Hx =
1 - 2z2x 1 - 2zx2 ,
x = 1 +
23 z2x3
1 — 4zx2
(4.1)
Remark 4.3. Here we use x2 = x = n to denote a double root of A in convenience.
Since Darboux's Theorem [2, Theorem 4] shows that the dominating singularity (i.e., that corresponds to the convergence radius) of the power series expansion of an enumerating function of a type of maps contains a lot of information about the number of maps considered, we have to locate the wanted singularity. By the definition of Fp(4) we have the following
Fact 4.4. The singularities of Fp(4) satisfy either
(1)	f - 1=0 or
(2)	x = 0 or
(3)	vx = 1 or
(4)	Equations (4.1).
From the above fact we may conclude that the dominating singularity of Fp(4) must satisfy (4.1). We now investigate the singularities of (4.1). The equation on the right hand side of (4.1) may be rewritten as
S(x, z) = (z2 + 4z)x3 - 4zx2 - x +1 = 0.
(4.2)
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	67
By the implicit function theorem [24, Theorem 1.3.1], (4.2) will determine a function x = x(z) with its singularities also satisfying dS^X'z) = 0. From this we may obtain a group of equations as
(z2 + 4z)x3 — 4zx2 — x + 1=0,
, 2 ^ 2	(4.3)
3(z2 +4z)x2 - 8zx - 1=0. The variable z may be extracted from (4.3) such that
3- 2x
4x2
Now we substitute it into an equation of (4.3) and obtain another high order equation of x:
3(3 - 2x)2 + 48x2(3 - 2x) - 32x(3 - 2x) - 16x2 = 0.	(4.4)
Factoring the left hand side of (4.4) yields
(-8x + 9)(2x - 1)2 =0.
One may see that the only possible singularity satisfying Facts 4.1 and 4.2 is z = 2y (which corresponds to x = |).
In order to apply Darboux's Theorem we also need to investigate the behavior of x = x(z) near the dominating singularity m = 2y. Since both d SXX'z) and dSgXX'z) are not equal to zero (where the function S(x, z) is defined by the Lagrangian inversion formula in (4.2)) at m, x = x(z) may be expanded into a power series of (1 - m)3 near m. Let
1	3
x = a + b( 1 - — ) + c( 1 - — ) + 1 - — ) ,
\m/	Vm/\m/	(45)
z = m — ml 1--
Substitute those into the equation system (4.3) and set the coefficients of (1 - m ) and (1 - m )3 to zero we obtain a group of relations such as
4
a = —, 27'
b2 = 2L,
256'
6ma2 - 3mb2 + 12a2 - 12b2 - 8a
C = -;-;-,
2(3ma + 12a - 4)
203V3 16 '
d =
We now begin to study the asymptotic behavior of Fp(4) near m. By Theorem B and Darboux's Theorem, we have the following
Fact 4.5. The coefficients of Fp(4) will be dominated by those of —Xf, when the number of faces is sufficiently large.
m
106
Ars Math. Contemp. 18 (2020) 105-115
Remark 4.6. Although there are several other terms in the expression of Fp(4) in Theorem B which will contribute several corresponding coefficients to the power series of Fp(4) by the famous transfer theorem discussed by Flajolet and Odlyzko [13], their effects may be ignored when the number of faces is large enough.
Let u = A./1 — —. Then the coefficient of u0 in 1 — 4zx2 f is
V	m	J
1 — 4 ma
1 — am 1 — 2 ma2
0,
a = -,
8'
27'
Now we concentrate on the evaluation of the coefficient of u in 1 — 4zx2 f. After many manipulations we see that this number is

b(3 — 2ma2) a(1 — 2ma2) '
which implies that
, — £-2=$ (
,1 — "I 4
a(1 — 2ma2p m)
Substitute this into (4.3) we see that
•y/1 — 4zx2f x(1 — f )
b(3—2ma2 ) a(1-2ma2 ) ma2 (1-2a) 1 —2ma2
1 — 4
m
This together with the Darboux's Theorem concludes the following
Theorem C. The number of rooted 4-edge-connected 4-regular maps on the projective plane with n inner faces is asymptotic to
C

n5 mnr( — I )
where r(x) is the gamma function at x and
C -
b(3 — 2ma2) a(1 — 2ma2)

ma2(1-2a) 1 — 2 ma2
and
27, |b
3V3
'
Here the sign of the number b is chosen to guarantee that the number C is a real number.
Remark 4.7. Although is very close to j§6, the dominating singularity corresponding to the rooted 2-connected loopless 4-regular maps on Ni, almost all the maps of such type are not 4-edge-connected by Theorem C, that is, nearly all of such maps must contain at least one separating cycle.
9
4
m=
a = -
m
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	69
References
[1]	D. Arqués, Relations fonctionnelles et dénombrement des cartes pointées sur le tore, J. Comb. Theory Ser. B 43 (1987), 253-274, doi:10.1016/0095-8956(87)90002-5.
[2]	E. A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485-515, doi:10. 1137/1016082.
[3]	E. A. Bender and E. R. Canfield, The number of rooted maps on an orientable surface, J. Comb. Theory Ser. B 53 (1991), 293-299, doi:10.1016/0095-8956(91)90079-y.
[4]	E. A. Bender, E. R. Canfield and L. B. Richmond, The asymptotic number of rooted maps on a surface. II. Enumeration by vertices and faces, J. Comb. Theory Ser. A 63 (1993), 318-329, doi:10.1016/0097-3165(93)90063-e.
[5]	E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull. 31 (1988), 257-271, doi:10.4153/cmb-1988-039-4.
[6]	E. A. Bender, Z. Gao and L. B. Richmond, Almost all rooted maps have large representativity, J. Graph Theory 18 (1994), 545-555, doi:10.1002/jgt.3190180603.
[7]	E. A. Bender and L. B. Richmond, A survey of the asymptotic behaviour of maps, J. Comb. Theory Ser. B 40 (1986), 297-329, doi:10.1016/0095-8956(86)90086-9.
[8]	J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
[9]	W. G. Brown, Enumeration of non-separable planar maps, Canadian J. Math. 15 (1963), 526545, doi:10.4153/cjm-1963-056-7.
[10]	W. G. Brown, Enumeration of quadrangular dissections of the disk, Canadian J. Math. 17 (1965), 302-317, doi:10.4153/cjm-1965-030-1.
[11]	W. G. Brown, On the existence of square roots in certain rings of power series, Math. Ann. 158 (1965), 82-89, doi:10.1007/bf01370732.
[12]	G. Chapuy, M. Marcus and G. Schaeffer, A bijection for rooted maps on orientable surfaces, SIAM J. Discrete Math. 23 (2009), 1587-1611, doi:10.1137/080720097.
[13]	P. Flajoletand A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216-240, doi:10.1137/0403019.
[14]	Z. Gao, The number of rooted 2-connected triangular maps on the projective plane, J. Comb. Theory Ser. B 53 (1991), 130-142, doi:10.1016/0095-8956(91)90058-r.
[15]	Z. Gao, The asymptotic number of rooted 2-connected triangular maps on a surface, J. Comb. Theory Ser. B 54 (1992), 102-112, doi:10.1016/0095-8956(92)90068-9.
[16]	Z. Gao and L. B. Richmond, Root vertex valency distributions of rooted maps and rooted triangulations, European J. Combin. 15 (1994), 483-490, doi:10.1006/eujc.1994.1050.
[17]	Z. Gao and J. Wang, Exact enumeration of rooted 3-connected triangular maps on the projective plane, Discrete Appl. Math. 141 (2004), 149-159, doi:10.1016/s0166-218x(03)00375-5.
[18]	Z. Gao and N. C. Wormald, The distribution of the maximum vertex degree in random planar maps, J. Comb. Theory Ser. A 89 (2000), 201-230, doi:10.1006/jcta.1999.3006.
[19]	I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, A Wiley-Interscience Publication, John Wiley & Sons, New York, 1983.
[20]	H. Grotzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 109-120.
[21]	J. P. Hutchinson, Automorphism properties of embedded graphs, J. Graph Theory 8 (1984), 35-49, doi:10.1002/jgt.3190080105.
106	Ars Math. Contemp. 18 (2020) 105-115
[22]	F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Ser. B 26 (1979), 205-216, doi:10.1016/0095-8956(79)90057-1.
[23]	F. Jaeger, Nowhere-zero flow problems, in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory 3, Academic Press, San Diego, California, pp. 71-95, 1988.
[24]	S. G. Krantz and H. R. Parks, The Implicit Function Theorem: History, Theory, and Applications, Modern Birkhauser Classics, Birkhauser/Springer, New York, 2013, doi:10.1007/ 978-1-4614-5981-1.
[25]	V. A. Liskovets, Some asymptotical estimates for planar Eulerian maps, Combin. Probab. Com-put. 5 (1996), 131-138, doi:10.1017/s0963548300001929.
[26]	Y. Liu, A polyhedral theory on graphs, Acta Math. Sinica (N. S.) 10 (1994), 136-142, doi: 10.1007/bf02580420.
[27]	Y. Liu, Combinatorial invariants on planar graphs, Acta Math. Sinica (N. S.) 11 (1995), 211220, doi:10.1007/bf02274063.
[28]	Y. Liu, Enumerative Theory of Maps, volume 468 of Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 1999.
[29]	Y.-P. Liu, Rectilinear Embeddings: Theory and Methods (in Chinese), Science Press, Beijing, 1994.
[30]	S. Long and H. Ren, Counting 2-connected 4-regular maps on the projective plane, Electron. J. Combin. 21 (2014), #P2.51 (24 pages), https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v21i2p51.
[31]	S. D. Long and H. Ren, 4-edge-connected 4-regular maps on the plane, Research-Report IMSU 90 (2001).
[32]	Maplesoft, a division of Waterloo Maple Inc., Maple, https://www.maplesoft.com/.
[33]	A. Mednykh and R. Nedela, Enumeration of unrooted maps of a given genus, J. Comb. Theory Ser. B 96 (2006), 706-729, doi:10.1016/j.jctb.2006.01.005.
[34]	A. Mednykh and R. Nedela, Enumeration of unrooted hypermaps of a given genus, Discrete Math. 310 (2010), 518-526, doi:10.1016/j.disc.2009.03.033.
[35]	R. C. Mullin and P. J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Comb. Theory 4 (1968), 259-276, doi:10.1016/s0021-9800(68)80007-9.
[36]	H. Ren and Y. Liu, On the number of regular maps on the projective plane, Util. Math. 56 (1999), 201-209.
[37]	H. Ren and Y. Liu, 4-regular maps on the Klein Bottle, J. Comb. Theory Ser. B 82 (2001), 118-137, doi:10.1006/jctb.2000.2030.
[38]	H. Ren and Y. Liu, Enumerating near-4-regular maps on the sphere and the torus, Discrete Appl. Math. 110 (2001), 273-288, doi:10.1016/s0166-218x(00)00251-1.
[39]	H. Ren and Y. Liu, The number of loopless 4-regular maps on the projective plane, J. Comb. Theory Ser. B 84 (2002), 84-99, doi:10.1006/jctb.2001.2064.
[40]	H. Ren, Y. Liu and Z. Li, Enumeration of 2-connected loopless 4-regular maps on the plane, European J. Combin. 23 (2002), 93-111, doi:10.1006/eujc.2001.0533.
[41]	L. B. Richmond and N. C. Wormald, Almost all maps are asymmetric, J. Comb. Theory Ser. B 63 (1995), 1-7, doi:10.1006/jctb.1995.1001.
[42]	W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. 51 (1949), 474-483, doi:10.1112/plms/s2-51.6.474.
[43]	W. T. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221-230, doi:10.1112/jlms/s1-36.1.221.
S. Long and H. Ren: 4-edge-connected 4-regular maps on the projective plane	71
[44]	W. T. Tutte, A theory of 3-connected graphs, Indag. Math. (Proceedings) 64 (1961), 441-455, doi:10.1016/s1385-7258(61)50045-5.
[45]	W. T. Tutte, A census of slicings, Canadian J. Math. 14 (1962), 708-722, doi:10.4153/ cjm-1962-061-1.
[46]	W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249-271, doi:10.4153/ cjm-1963-029-x.
[47]	W. T. Tutte, On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 (1968), 64-74, doi:10.1090/s0002-9904-1968-11877-4.
[48]	W. T. Tutte, Graph Theory, volume 21 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, Massachusetts, 1984.
[49]	T. R. S. Walsh, A. Giorgetti and A. Mednykh, Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices, Discrete Math. 312 (2012), 2660-2671, doi: 10.1016/j.disc.2011.11.027.
[50]	T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory Ser. B 13 (1972), 192-218, doi:10.1016/0095-8956(72)90056-1.
[51]	T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. II, J. Comb. Theory Ser. B 13 (1972), 122-141, doi:10.1016/0095-8956(72)90049-4.
[52]	N. H. Xuong, How to determine the maximum genus of a graph, J. Comb. Theory Ser. B 26 (1979), 217-225, doi:10.1016/0095-8956(79)90058-3.