Fu he esul s on andom cubic plana g aphs
Ma c Noy ∗Cl´emen Requil´e †Juanjo Ru´e ‡
Abs ac
We p o ide p ecise asymp o ic es ima es o he numbe o se e al classes o labeled cubic plana
g aphs, and we analyze p ope ies o such andom g aphs unde he uni o m dis ibu ion. This model
was i s analyzed by Bodi sky e al. (Random S uc u es Algo i hms 2007). We e isi hei wo k and
ob ain new esul s on he enume a ion o cubic plana g aphs and on andom cubic plana g aphs. In
pa icula , we de e mine he exac p obabili y o a andom cubic plana g aph being connec ed, and we
show ha he dis ibu ion o he numbe o iangles in andom cubic plana g aphs is asymp o ically
no mal wi h linea expec a ion and a iance. To he bes o ou knowledge, his is he i s ime one
is able o de e mine he asymp o ic dis ibu ion o he numbe o copies o a ixed g aph con aining a
cycle in classes o andom plana g aphs a ising om plana maps.
1 In oduc ion and summa y o esul s
The enume a ion o labeled plana g aphs has been ecen ly he subjec o much esea ch; see [11, 12] o
su eys on he a ea. The p oblem o coun ing plana g aphs was i s sol ed by Gim´enez and Noy [6], while
cubic plana g aphs whe e enume a ed by Bodi sky, Kang, L¨o le and McDia mid [2]. Mo e ecen ly, he
p esen au ho s sol ed he p oblem o enume a ing 4- egula plana g aphs [14]. Se e al open p oblems
emain, like he enume a ion o bipa i e o iangle- ee plana g aphs.
The goal o his pape is o sha pen he esul s om [2], as well as o p o e new esul s. We i s enume a e
asymp o ically se e al classes o labeled cubic plana g aphs. Among ou new esul s a e he enume a ion
o cubic plana mul ig aphs and o iangle- ee cubic plana g aphs. In o de o achie e his goal we need
o use he so-called Dissymme y Theo em o coun ing un oo ed g aphs whose s uc u e can be encoded by
means o a decomposi ion ee.
Random cubic plana g aphs a e analyzed acco ding o he uni o m dis ibu ion. Mo e p ecisely, le G
be he class o labeled cubic plana g aphs and le gnbe he numbe o g aphs in Gwi h n e ices. Then
each g aph in Gwi h n e ices is aken wi h he same p obabili y 1/gn. We ob ain he exac p obabili y
ha a andom cubic plana g aph is connec ed, and we p o e se e al esul s on he dis ibu ion o he
numbe o copies o a ixed subg aph. In pa icula , we show ha he dis ibu ion o he numbe o iangles
is asymp o ically no mal wi h linea expec a ion and a iance. To he bes o ou knowledge, his is he
i s ime one is able o de e mine he asymp o ic dis ibu ion o he numbe o copies o a ixed g aph H
con aining a cycle in classes o andom plana g aphs a ising om plana maps. We also ob ain Gaussian
limi laws o he numbe o copies o ce ain almos cubic subg aphs.
∗Uni e si a Poli `ecnica de Ca alunya and Ba celona G adua e School o Ma hema ics, Depa men o Ma hema ics, Edi ici
Omega, 08034 Ba celona, Spain. E-mail: [email p o ec ed]. Suppo ed by he Spanish Minis e io de Econom´ıa y Compe i-
i idad p ojec s MTM2014-54745-P, MTM2017-82166-P and MDM-2014-0445.
†Ins i u e o Algeb a, Johannes Keple Uni e si ¨a Linz, Aus ia. E-mail: [email p o ec ed]. Suppo ed by he
Aus ian Science Fund (FWF) g an F5004. The wo k p esen ed in his pape was ca ied ou while he au ho was a ilia ed
wi h he Ins i u ¨u Ma hema ik und In o ma ik, F eie Uni e si ¨a Be lin, and Be lin Ma hema ical School, Ge many, and
pa ially suppo ed by he Ma ie Cu ie Ca ee In eg a ion G an FP7 PEOPLE - 2013-CIG 630749 - Coun g aph.
‡Uni e si a Poli `ecnica de Ca alunya and Ba celona G adua e School o Ma hema ics, Depa men o Ma hema ics, Edi ici
Omega, 08034 Ba celona, Spain. E-mail: [email p o ec ed]. Suppo ed by he Spanish Minis e io de Econom´ıa y
Compe i i idad p ojec MTM2014-54745-P, MTM2017-82166-P and he Ma ie Cu ie Ca ee In eg a ion G an FP7 PEOPLE
- 2013-CIG 630749 - Coun g aph.
1
The p oo s a e based on combina o ial decomposi ions, gene a ing unc ions and asymp o ic analysis o
hei coe icien s, using he ools o analy ic combina o ics [5]. In se e al places we use Maple o pe o m
symbolic and nume ical compu a ions.
1.1 Resul s on enume a ion
In he i s place we ob ain an asymp o ic es ima e o he numbe cno connec ed cubic plana g aphs.
In all he s a emen s ha ollow, nshould be e en since a cubic g aph has necessa ily an e en numbe o
e ices. To a oid epe i ion, we assume his is always he case when e e ing o he numbe o e ices in
cubic g aphs. All he nume ical cons an s in his pape a e gi en wi h a p ecision o 6 decimals places.
Theo em 1. The numbe cno connec ed cubic plana g aphs wi h n e ices is asymp o ically
cn∼c·n−7/2γnn!,
whe e c≈0.060973 and γ=ρ−1≈3.132591, whe e ρ≈0.319225 is he smalles posi i e oo o he equa ion
729x12 + 17496x10 + 148716x8+ 513216x6−7293760x4+ 279936x2+ 46656 = 0.(1)
Nex we es ima e he numbe o all cubic plana g aphs.
Theo em 2. The numbe gno cubic plana g aphs wi h n e ices is asymp o ically
gn∼g·n−7/2γnn!,
whe e γis as in Theo em 1 and g≈0.061010. As a consequence, he limi ing p obabili y p ha a andom
cubic plana g aph is connec ed is equal o
p=c
g≈0.999397.
We ema k ha he ac ual alue o pwas no compu ed in [2], only es ima ed om alues o cnand gn
o small n. As we will see la e , pcan be compu ed exac ly using he Dissymme y Theo em. Once we ha e
he alue o p, a s anda d p oo (see [7]) shows ha he numbe o connec ed componen s in a andom cubic
g aph is asymp o ically dis ibu ed as X+ 1, whe e Xis a Poisson law o pa ame e λ≈0.000604.
I is also possible o es ima e he numbe o 2-connec ed cubic plana g aphs.
Theo em 3. Le bnbe he numbe o 2-connec ed cubic plana g aphs on n e ices. Then
bn∼b·n−7/2γn
bn!,
whe e b≈0.059244,γb=ρ−1
b≈3.129666, whe e ρb≈0.319523 is he smalles posi i e solu ion o
54x6+ 324x4−4265x2+ 432 = 0.
Ou nex esul is an es ima e on he numbe o cubic plana mul ig aphs. This class o g aphs is
ins umen al in he s udy o he phase ansi ion o he E d˝os-R´enyi andom g aph [8, 9, 13]. In hese
e e ences cubic mul ig aphs a e equipped wi h a weigh ha depends on he numbe o loops and mul iple
edges. He e we coun unweigh ed cubic mul ig aphs, which is a esul in e es ing by i sel .
Theo em 4. The numbe hno cubic plana mul ig aphs is asymp o ically
hn∼h·n−7/2γn
mn!,
wi h h≈0.224743 and γm=ρ−1
m≈3.985537, whe e ρm≈0.250907 is he smalles posi i e oo o he
equa ion
729 x12 −17496 x10 + 148716 x8−513216 x6−7293760 x4−279936 x2+ 46656 = 0.(2)
2
The same es ima e holds o he numbe o connec ed cubic plana mul ig aphs, bu wi h h eplaced by he
cons an h0≈0.209410. The limi ing p obabili y o connec i i y is
pm=h0
h≈0.931778.
We ema k ha he p oo needs again an applica ion o he Dissymme y Theo em, since he p esence o
loops and mul iple edges does no allow us, as o simple g aphs, o di ec ly ela e he numbe o g aphs
oo ed a a e ex wi h hose oo ed a an edge. In addi ion, he simila i y be ween equa ions (1) and (2)
will be explained la e .
We ecall ha a sequence (an) is P- ecu si e i i sa is ies a linea ecu ence ela ion whose coe icien s
a e polynomials in n.
Theo em 5. The ollowing sequences a e P- ecu si e: he numbe s o a bi a y, connec ed and 2-connec ed
cubic plana g aphs, and he numbe o cubic plana mul ig aphs.
The p oo s ely on he algeb aic cha ac e o se e al o he gene a ing unc ions in ol ed and, in he case
o cubic mul ig aphs, on a u he applica ion o he Dissymme y Theo em.
Ou las esul in his sec ion is he enume a ion o iangle- ee cubic plana g aphs. The p oo is mo e
in ol ed and will be gi en a e he p oo o Theo em 7, since i uses he echniques in oduced he e o
s udying he dis ibu ion o he numbe o iangles in andom cubic plana g aphs.
Theo em 6. The numbe uno connec ed iangle- ee cubic plana g aphs wi h n e ices is asymp o ically
n∼ ·n−7/2γn
n!,
wi h ≈0.000911 and γ =ρ−1
≈2.641747, whe e ρ ≈0.378537 is he smalles posi i e solu ion o he
equa ion
x40 −2x38 −41x36 + 180x34 + 285x32 −3630x30 −26651
4x28 +5654783
32 x26
−3989098451
4096 x24 +50409552353
16384 x22 −246713078305261
37748736 x20 +8988271236666325
905969664 x18
−34616066062430108809
3131031158784 x16 +148714112813428613
16307453952 x14 −88102457851295
15925248 x12
+28819599609215
11943936 x10 −2805808889
3888 x8+130387637
972 x6−8646784
729 x4−128x2+ 64 = 0.
(3)
In addi ion, he numbe no iangle- ee cubic plana g aphs wi h n e ices is asymp o ically
n∼α·n−7/2γn
n!,
whe e α≈0.0009109.
The mul iplica i e cons an αin he las heo em is he only cons an in ou wo k o which we do no
ob ain an exac exp ession. I would be in p inciple possible o ob ain his exp ession, bu he compu a ions
would be e y complex. The app oxima e alue gi en in he s a emen is es ima ed om small alues o n.
A he end o he pape we p o ide a able wi h he numbe s o cubic plana g aphs o small alues o n
o he new amilies we ha e enume a ed: mul ig aphs and iangle- ee g aphs. The numbe s o a bi a y,
connec ed and 2-connec ed cubic plana g aphs a e lis ed in [2].
1.2 Resul s on limi laws
Gi en an unlabeled g aph H, a copy o Hin a labeled g aph Gis a subg aph isomo phic o H. Ou esul s
in his sec ion deal wi h he numbe o copies o a ixed subg aph. We s a wi h he numbe o iangles,
he main esul in his sec ion. We say ha a sequence Xno andom a iables is asymp o ically no mal i
he s anda dized a iables (Xn−E[Xn])/σ(Xn) con e ge in dis ibu ion o he s anda d no mal law.
3
Theo em 7. Le Xnbe he numbe o iangles in a andom cubic plana g aph. Then Xnis asymp o ically
no mal wi h momen s
E[Xn]∼µn, Va [Xn]∼λn,
whe e
µ≈0.121974, λ ≈0.064985.
I was p o ed in [2] ha Xnis linea wi h high p obabili y. Ou esul is a conside able sha pening o his
ac . The p oo , based on he so-called Quasi-powe s Theo em, is echnically in ol ed and we a e no able
o ex end i , o ins ance, o he numbe o cycles o leng h 4. The key p ope y he e is ha wo iangles
in a cubic g aph a e ei he e ex disjoin o sha e one edge.
Ou inal esul s conce n he numbe o copies o g aphs which a e close o being cubic. We de ine a
che y as a plana g aph in which all e ices ha e deg ee 3 excep o one e ex o deg ee 1. The smalles
che y has 6 e ices and is ob ained by subdi iding one edge o K4and a aching one e ex o deg ee 1. In
wha ollows, we deno e by au (H) he numbe o au omo phisms o a g aph H. We ecall ha he numbe
o di e en ways o labeling an unlabeled g aph His equal n!/au (H).
Theo em 8. Le XH,n be he numbe o copies o a ixed unlabeled che y Hwi h h e ices in a andom
cubic plana g aph. Then XH,n is asymp o ically no mal wi h momen s
E[XH,n]∼µn, Va [XH,n]∼λn,
whe e
µ=4374(ρ4+ 8ρ+ 4)2
ρ2P1·ρh
au (H), λ =8748(ρ4+ 8ρ+ 4)(P2h+P3)
ρ4P3
1·ρ2h
au (H)2+µ+µ2,
whe e ρis as in Theo em 1, and
P1=−(2187ρ10 + 43740ρ8+ 297432ρ6+ 769824ρ4−7293760ρ2+ 139968) >0,
P2=−4374 ρ4+ 8 ρ2+ 43P1,
P3=−14348907ρ22 −593088156ρ20 −10235553660ρ18 −95276742480ρ16 −464803389936ρ14
−412656456960ρ12 + 7449015918528ρ10 + 32947458310656ρ8−457978474586624ρ6
+18919725382656ρ4+ 3101861081088ρ2−19591041024.
Mo eo e , o h≥2we ha e ha λ > 0.
I was shown in [10] ha , wi h high p obabili y, XH,n is a leas cn o some cons an c > 0 ha depends
only on H. Ou esul p o ides a p ecise limi dis ibu ion.
De ine a b ick as a g aph ob ained om a 3-connec ed cubic plana g aph by emo ing one edge, so
ha all e ices ha e deg ee 3 expec wo e ices uand ha ha e deg ee 2, and such ha uand a e
dis inguishable (as i he edge emo ed was o ien ed). Ou las esul gi es he dis ibu ion o he numbe
o copies o a gi en b ick. We deno e by K−
4 he g aph ob ained om K4by emo ing one edge.
Theo em 9. Le XB,n be he numbe o copies o a ixed unlabeled b ick B, di e en om K−
4, wi h b
e ices in a andom cubic plana g aph. Then XB,n is asymp o ically no mal wi h momen s
E[XB,n]∼µn, Va [XB,n]∼λn,
whe e
µ=10185312ρ2
P1
ρb
au (B), λ =242688ρ2(P2h+P3)
P3
1
ρ2b
au (B)2+µ+µ2,
4
ρis as in Theo em 1, and
P1=−(2187ρ10 + 43740ρ8+ 297432ρ6+ 769824ρ4−7293760ρ2+ 139968) >0,
P2=−854929626ρ2P1,
P3= 880066296 ρ20 + 35202651840 ρ18 + 591404550912 ρ16 + 5407127322624 ρ14
+19994308272243 ρ12 −51726289953708 ρ10 −559899907432200 ρ8−1063749220662816 ρ6
−5760872476783424 ρ4+ 43131140739648 ρ2+ 3604751548416.
Mo eo e , o b≥2we ha e ha λ > 0.
The same esul holds o B=K−
4wi h cons an s
µ≈0.004529, λ ≈0.004343.
The case when B=K−
4has o be ea ed sepa a ely, since i can appea in wo di e en ways: as a
3-connec ed co e, o as he pa allel composi ion o wo loop ne wo ks, as explained in he nex sec ion. B icks
o he han K−
4can only appea as 3-connec ed co es.
We ha e ob ained simila esul s o pa ame e s ha ha e been s udied o se e al classes o plana and
ela ed classes o g aphs [7]. We can show ha he numbe o cu e ices, he numbe o is hmuses (sepa a -
ing edges) and he numbe o blocks (2-connec ed componen s, including is hmuses) a e all asymp o ically
no mal wi h linea expec a ion and a iance. Fo he sake o b e i y we omi he p oo s and gi e only he
alues o he cons an s o he expec a ion and a iance:
Pa ame e µ λ
Cu e ices 0.001877 0.003793
Is hmuses 0.000939 0.000950
Blocks 0.001878 0.003796
2 P elimina ies
In his sec ion we collec a numbe o analy ic and combina o ial esul s ha a e needed in he sequel.
Analy ic combina o ics. We use he elemen s o analy ic combina o ics as in [5]. To a class Go labeled
g aphs, we associa e he exponen ial gene a ing unc ion G(x) = Pn≥0gnxn/n!, whe e gnis he numbe o
g aphs in Gwi h n e ices. We de ine G•as he class o g aphs in Gwi h a dis inguished e ex ( ha we
call he oo ). By he basic ules o he symbolic me hod, i s gene a ing unc ion is G•(x) = xG0(x).
Gi en a complex numbe ζ6= 0, a ∆-domain a ζis an open se in he complex plane o he o m
∆(R, φ) = {z:|z|< R, z 6=ζ, |a g(z−ζ)|> φ}.
A dominan singula i y o a complex unc ion is a singula i y o he smalles modulus. The basic ool o
ex ac ing asymp o ic es ima es om gene a ing unc ions is he ollowing (see [5, Co olla y VI.1]).
Lemma 10 (T ans e Theo em).Assume ha (z)has a unique dominan singula i y ρ > 0and is analy ic
in a ∆-domain a ρ. I sa is ies, locally a ound ρ, he es ima e
(z)∼
z→ρ(1 −z/ρ)−α,
wi h α6∈ {0,−1,−2, . . . }, hen he coe icien s o (z)sa is y
[zn] (z)∼
n→∞
nα−1
Γ(α)ρ−n.
5

I has se e al dominan singula i ies coming om pu e pe iodici ies, hen he con ibu ions om each
o hem mus be combined (see [5, IV.6.1]). In ou case, he pe iodici ies a e due o he ac ha cubic
g aphs ha e necessa ily an e en numbe o e ices and he co esponding gene a ing unc ions a e e en. We
will loca e he (unique) posi i e dominan singula i y ρand will add he con ibu ions om ρand −ρ.
All he singula i ies we will encoun e a e o squa e- oo ype, ha is, he expansion o a unc ion a a
singula i y ρis o he o m
(x) = X
i≥0
iXi, X =p1−x/ρ.
The singula expansions we encoun e a e o he o m
(z) = 0+ 2X2+···+ 2kX2k+ 2k+1X2k+1 +O(X2k+2),
wi h k= 1 o k= 2. The only non-analy ic e m is 2k+1X2k+1, and i is om his e m ha asymp o ic
es ima es a e de i ed using he T ans e Theo em.
In o de o p o e asymp o ic no mal limi laws, we need a simpli ied e sion o he so-called Quasi-powe s
Theo em (see [5, Theo em IX.8]).
Lemma 11 (Quasi-powe s Theo em).Le {Xn}n≥1be a sequence o non-nega i e disc e e andom a iables
wi h p obabili y gene a ing unc ions pn(u). Assume ha , uni o mly in a ixed complex neighbo hood o u= 1
pn(u) = A(u)∆B(u)n1 + On−1,
whe e A(u), B(u)a e analy ic a u= 1 and A(1) = B(1) = 1. Assume inally ha B(u)sa is ies he condi ion
B00(1) + B0(1) −B0(1)26= 0.
Then he dis ibu ion o Xnis, a e s anda diza ion, asymp o ically no mal, and he mean and a iance
sa is y
E[Xn]∼B0(1)n, Va [Xn]∼B00(1) + B0(1) −B0(1)2n.
In ou applica ions we will ha e B(u) = ρ(1)/ρ(u), whe e ρ(u) will be he dominan singula i y (as a
unc ion o z) o a bi a ia e gene a ing unc ion (z, u). The o me exp essions hen become
E[Xn]∼−ρ0(1)
ρ(1) n, Va [Xn]∼ −ρ00(1)
ρ(1) −ρ0(1)
ρ(1) +ρ0(1)
ρ(1) 2!n.
Plana maps and iangula ions. We ecall ha a plana map is a connec ed plana mul ig aph em-
bedded in he plane up o homeomo phism. A map is oo ed i one o i s edges is dis inguished and o ien ed.
In his way a oo ed map has a oo edge and a oo e ex ( he ail o he oo edge). We de ine he oo
ace as he ace o he igh o he di ec ed oo edge. A oo ed map has no au omo phism, in he sense ha
e e y e ex, edge and ace is dis inguishable. F om now on all maps a e plana and oo ed. Since maps a e
no labeled, he associa ed gene a ing unc ions a e o dina y.
A map is a iangula ion i i is 3-connec ed and e e y ace is a iangle (one can conside mo e gene al
iangula ions ha ing loops and mul iple edges bu hey a e no needed in his pape ). The dual o a
iangula ion is a 3-connec ed cubic map, since 3-connec i i y in maps is p ese ed unde duali y (a map
is 3-connec ed i i is 3-connec ed as a g aph and i has no mul iple edges). Le T(z) be he (o dina y)
gene a ing unc ion o 3-connec ed iangula ions oge he wi h he map consis ing o a iangle, whe e he
a iable zma ks he numbe o e ices minus wo. Then, as shown by Tu e [16],
T(z) = U(z) (1 −2U(z)) ,(4)
whe e Uis an algeb aic unc ion de ined by
z=U(z)(1 −U(z))3.(5)
6
Equa ion (5) has a unique solu ion wi h posi i e coe icien s, gi en by
U(z) = z+ 3z2+ 15z3+ 91z4+···
Then
T(z) = z+z2+ 3z3+ 13z4+···
As shown in [16], he unique singula i y o U(and hence o T) is loca ed a τ= 27/256. In pa icula ,
U(τ)=1/4, T(τ)=1/8.
The singula expansion o U(z) a τis equal o
U(z) = 1
4−√6
8Z+1
12Z2−31√6
1728 Z3+37
1296Z4−2093√6
248832 Z5+O(Z6),(6)
whe e Z=p1−z/τ. F om Equa ion (4) we ob ain he singula expansion o T(z) a τ
T(z) = 1
8−3
16Z2+√6
24 Z3−13
192Z4+35√6
1728 Z5+O(Z6).
We also need o conside he amily o 4-connec ed iangula ions, which a e hose no con aining a
sepa a ing iangle (a iangle ha is no a ace) and ha ing a leas 6 e ices. The smalles 4-connec ed
iangula ion is he g aph o he oc ahed on. The associa ed gene a ing unc ion T4(z), whe e again zma ks
e ices minus wo, is equal o (see [16])
T4(z) = z+V(z)(V(z)−1)(V(z) + 1)−2−z2,(7)
whe e V(z) is gi en by
z=V(z)(1 −V(z))2.
The unique solu ion wi h posi i e coe icien s is
V(z) = z+ 2z2+ 7z3+ 30z4+. . . ,
and
T4(z) = z4+ 3z5+ 12z6+ 52z7+. . .
The unique singula i y o T4is a ς= 4/27 and we ha e
V(ς)=1/3, T4(ς)=7/5832.
The singula expansion o V(z) a ςis equal o
V(z) = 1
3−2√3
9Z+2
27Z2−5√3
243 Z3+16
729Z4−77√3
8748 Z5+O(Z6), Z =p1−z/ς.
As be o e, using (7) we ob ain
T4(z) = 7
5832 −245
23328Z2+√3
96 Z3−833
93312Z4−√3
864Z5+O(Z6).
7
3-connec ed cubic plana g aphs. Le M(x, y) be he GF o labeled 3-connec ed cubic plana g aphs
oo ed a a di ec ed edge, whe e xma ks e ices and yma ks edges. The e is a bijec ion be ween iangu-
la ions and plana 3-connec ed cubic maps gi en by duali y. Also, by Whi ney Theo em, e e y 3-connec ed
cubic plana g aph admi s a unique embedding in he plane up o o ien a ion. Using his ac we can exp ess
M(x, y) in e ms o he gene a ing unc ion T(z) o oo ed unlabeled iangula ions, whe e zcoun s he
numbe o e ices minus wo. The ela ion is
M(x, y) = 1
2T(x2y3)−x2y3.(8)
The sub ac ed e m x2y3co esponds o he iangula ion consis ing o a single iangle. We ha e
M(x, y) = 12 x4
4! y6+ 1080 x6
6! y9+···
The i s monomial co esponds o K4(a unique labeling and 12 possible oo s) and he second one o he
iangula p ism (60 ways o label and 18 oo s).
We will also need he gene a ing unc ion M(x, y) o (un oo ed) labeled 3-connec ed cubic plana g aphs,
which is ob ained by in eg a ion. We ha e M(x, y)=2y∂M(x, y)/∂y, hence
M(x, y) = 1
2ZM(x, y)
ydy =1
4ZT(x2y3)−x2y3
ydy.
We change a iables as z=x2y3and a e le wi h he in eg al 1
12 RT(z)/z dz. We make he u he change
=U(z) and, using Equa ions (4) and (5), we ge
M(x, y) = 1
12 ZT(z)
zdz −z
=1
12 Z(1 −2 )(1 −4 )
1− d −z
=−1
12 4 2+ 2 + 3 log(1 − ) + z.
Hence
M(x, y) = −1
12 4U(x2y3)2+ 2U(x2y3) + 3 log(1 −U(x2y3)) + x2y3.(9)
Ne wo ks. We ollow he de ini ions om [2] bu de ia e sligh ly om he no a ion he e. A ne wo k is
a connec ed cubic plana mul ig aph Gwi h an o de ed pai o adjacen e ices (s, ) such ha he g aph
ob ained by emo ing he edge s is simple. The e could be an addi ional edge be ween sand which is no
emo ed. We no ice ha s can be a simple edge, a loop o a belong o a double edge. The o ien ed edge s
is he oo o he ne wo k and s, a e he poles.
Gi en a ne wo k H, wi h oo edge s , and a di ec ed edge e=u o ano he ne wo k G, he eplacemen
o ewi h His he ne wo k ob ained om Gby pe o ming he ollowing ope a ion. Subdi ide he edge u
wice p oducing a pa h uu0 0 , emo e he edge u0 0, and iden i y u0and 0, espec i ely, wi h e ices sand
o H−s . No ice ha i Gand Ha e cubic and plana , so is he esul ing ne wo k.
A cu e ex in a cubic g aph is necessa ily inciden wi h one o h ee is hmuses. Fo each cu e ex
uinciden wi h exac ly one is hmus e, we can emo e he componen con aining eand e ase he esul ing
e ex o deg ee 2 esul ing in a cubic g aph. We call his ope a ion supp essing he cu e ex u.
By classi ying he possible si ua ions ob ained by emo ing he edge s , ne wo ks all in o i e classes, as
shown in [2]. Fo he sake o comple eness we o e an al e na i e p oo based on Tu e’s decomposi ion o
2-connec ed g aphs in o 3-connec ed componen s [3].
Lemma 12. Le Gbe a ne wo k and le s be he oo edge. Then Gbelongs o one and only one o he
ollowing classes.
8
• L (Loop). The oo edge is a loop.
• I (Is hmus). The oo edge is an is hmus.
• S (Se ies). G−s is connec ed bu is no 2-connec ed.
• P (Pa allel). G−s is 2-connec ed and G−{s, }is no connec ed.
• H (3-connec ed). Gis ob ained om a 3-connec ed g aph by possibly eplacing each non- oo edge wi h
a ne wo k o ypes L,S,Po H.
P oo . Le Gbe a ne wo k wi h oo edge s , and suppose s is nei he a loop no an is hmus, so we a e
no in he classes Lo I. Conside he 2-connec ed co e Cob ained by supp essing all cu e ices inciden
wi h exac ly one is hmus. By Tu e’s decomposi ion in o 3-connec ed componen s, Cbelongs o ei he S,P
o H.
Le now Dbe he class o ne wo ks o which he g aph esul ing om he emo al o he oo edge
emains connec ed. I is by de ini ion,
D=L+S+P+H,
whe e + deno es he disjoin union o classes, and he class Iis excluded since emo ing he oo edge o
ne wo ks in his class disconnec s he g aph. Le hen L(x), I(x), S(x), P(x), H(x), D(x) be he associa ed
gene a ing unc ions.
The ollowing esul , based on simple combina o ial a gumen s, is shown in [2, Sec ion 3].
Lemma 13. The ollowing equa ions hold:
D=L+S+P+H,
L=x2
2(I+D−L),
S=D(D−S),
I=L2
x2,
P=x2D+x2
2D2,
H=M(x, 1 + D)
1 + D.
(10)
No ice ha all he unc ions in ol ed a e e en, in ag eemen wi h he ac ha a cubic g aph has an e en
numbe o e ices. Using he ela ions D−L=S+P+Hand D−S=L+P+H, he sys em (10) can be
ew i en so ha all he unc ions on he igh hand-side ha e non-nega i e coe icien s when expanded in
e ms o x, L, I, S, H and D. This is also ue o he equa ion H=M(x, 1 + D)/(1 + D), since M(x, y) is
di isible by y. I ollows (see [4]) ha he e is a unique solu ion o he sys em wi h non-nega i e coe icien s,
which is he combina o ial solu ion.
Le C(x) be he gene a ing unc ion o connec ed cubic plana g aphs, and C•(x) = xC0(x) ha o
connec ed g aphs oo ed a a e ex. As shown in [2], C•(x) can be exp essed in e ms o ne wo ks as
3C•(x) = D(x) + I(x)−L(x)−x2D(x)−L(x)2.(11)
The ac o 3 comes om double coun ing since a e e y oo e ex we ha e 3 possible oo edges wi h
as a ail. The e m D(x) + I(x) encodes all ypes o ne wo ks, om which one has o sub ac hose which
a e no simple. These a e L, whe e he oo edge is a loop, and hose whe e he oo edge is a double edge:
pa allel ne wo ks encoded by x2D(x), and se ies ne wo ks encoded by L(x)2.
9
Le now −→
B(x) be he gene a ing unc ion o 2-connec ed cubic plana g aphs oo ed a a di ec ed edge.
Then −→
B(x) = D(x)−x2D(x).
The eason is ha om he ne wo ks encoded by D(x) we ha e o exclude he pa allel ne wo ks wi h a
double edge, ha co espond o x2D(x). I now B•is he gene a ing unc ion o 2-connec ed e ex- oo ed
cubic g aphs, by double coun ing we ha e
B•(x) = −→
B(x)
3.
Applying he T ans e Theo em we ob ain o e en n
n·bn=n![xn]B•(x)∼2(1 −ρ2
b)D3
3·Γ(−3/2) ·n−5/2·ρ−n
bn!,
and om he e he es ima e on bn ollows wi h b=2(1−ρ2
b)D3
3·Γ(−3/2) ≈0.059244.
3.4 Cubic plana mul ig aphs
Simila ly o he simple case, we decompose connec ed cubic plana mul ig aphs using ne wo ks. In his
si ua ion we do no demand ha emo ing he edge be ween he poles gi es a simple g aph. We also use
he same no a ion o ne wo ks as be o e. The equa ions a e as ollows.
D=L+S+P+H,
L=x2+x2L+x2
2(I+D−L),
I=L2
x2,
S=D(D−S),
P=x2+x2D+x2D2
2,
H=M(x, 1 + D)
1 + D.
(16)
The only di e ences wi h he sys em o equa ions desc ibing he ne wo ks associa ed wi h simple g aphs a e
he e m x2, in he equa ion o P, encoding he 3-bond, and he e m x2(1 + L), in he equa ion o L,
encoding he cubic mul ig aph wi h wo e ices and wo loops, oo ed a a loop and whe e he non- oo ed
loop is possibly eplaced by a loop-ne wo k (see Figu e 3).
Figu e 3: Le is he only cubic mul ig aph wi h wo e ices and wo loops. Righ is he same mul ig aph
whose non- oo ed loop has been eplaced by a loop-ne wo k.
Using he same a gumen s as be o e, one can show ha he e exis s a unique solu ion wi h non-nega i e
coe icien s o he abo e sys em, which is he combina o ial solu ion.
Le C(x) be he gene a ing unc ion o connec ed cubic plana mul ig aphs. Due o he p esence o
mul iple edges and loops, he e is no di ec algeb aic ela ion exp essing C•(x) in e ms o ne wo ks. As in
Sec ion 3.2, we need o eso once mo e o he Dissymme y Theo em.
16

P oo o Theo em 4. We s a by ob aining a single equa ion o D om he sys em (16). Fi s , we
combine he second and he hi d equa ions and sol e o Las
L= 1 −x2
2− x4
4+ 1 −x2(D+ 3).
Then we ha e
D=D2
1 + D+x2+x2D+x2
2D2+ 1 −x2
2− x4
4+ 1 −x2(D+ 3) + M(x, 1 + D)
1 + D.
A simple manipula ion oge he wi h (8) gi es
F(x, D) = (1 + D) x4
4+ 1 −x2(D+ 3) −Tx2(1 + D)3
2−1=0.(17)
We ew i e as
Hx, D, T x2(1 + D)3=1 + 1
2Tx2(1 + D)32
−(1 + D)2x4
4+ 1 −x2(D+ 3)= 0,
whe e now His a polynomial. We p oceed as in he p oo s o Theo ems 1 and 3. Equa ions (17) and
x2(1 + D)3=τha e a unique posi i e solu ion
ρm≈0.250907 and D0=D(ρm)≈0.187679.
The minimal polynomial p(x) o D(x) is ob ained by elimina ion and is equal o he one in he s a emen .
We check ha ρmis a oo o p(x), oge he wi h he emaining analy ic condi ions o Lemma 15.
The es o he p oo is a u he applica ion o he Dissymme y Theo em and is e y simila o ha o
Theo em 2 wi h some small changes. The oo ed ee-decomposi ions a e he same, excep ha we ha e o
upda e he co esponding classes o encode he 3-bond and he mul ig aph wi h wo e ices and wo loops.
Those changes only a ec M-nodes and L-nodes. The new equa ion o he gene a ing unc ion associa ed
o M-nodes is hen
CM=x2
21 + D+D2
2+D3
6,
As o L-nodes, we need o in oduce wo new ypes o cu - e ices, hose adjacen o a loop o o a double
edge (see Figu e 4). The equa ion o he associa ed gene a ing unc ion becomes
CL=L+L2+L(D−L)
2+L3
6x2.
Now when he ee is ei he oo ed a an edge o a an o ien ed edge, we need o conside he new case
when wo cu - e ices a e connec ed by a double edge (see he mul ig aph on he igh o Figu e 4). The
co esponding equa ions a e gi en by
CL−L =L2
2x2+L2
2, CL→L =L2
x2+L2.
We hen apply Theo em 14 and, a e a s aigh o wa d calcula ion, ob ain
C(x) = x2
21 + D+D2
2+D3
6+M(x, 1 + D) + L3
6x2
−1
2log(1 −D+S) + D−S+(D−S)2
2+P(S+H) + HS +P2+H2
2+L2
x2+L2.
(18)
17
Figu e 4: In whi e a e he wo new ypes o cu - e ices in a mul ig aph. Tha a e espec i ely adjacen o
a loop (le ) and o a double edge ( igh ).
The Puiseux expansion a ρmis compu ed om ha o D(x) using he p e ious exp ession o C(x) and is
o he o m
C(x) = C0+C2X2+C4X4+C5X5+O(X6).
Since we do no ha e a singula expansion o C•(x) ha we can in eg a e as in he p oo o Theo em 2, we
need o show di ec ly ha C3= 0. Assume o con adic ion ha C36= 0. Then, by he T ans e Theo em,
he a io be ween he numbe o connec ed cubic plana mul ig aphs wi h n e ices and he numbe o
connec ed ne wo ks wi h n e ices would end o a cons an as ngoes o in ini y. Le us de ine a bad edge as
ei he a double edge o a loop. Fo n≥4, a e ex o a connec ed cubic plana mul ig aph can be adjacen
o a mos one bad edge. Hence each e ex is adjacen o a leas one simple edge, hence he e a e a leas
n/2 simple edges. Each ime a simple edge o a connec ed cubic plana mul ig aph is dis inguished and
di ec ed, we ge a di e en connec ed ne wo k, hence he numbe o connec ed ne wo ks wi h n e ices is
a leas n/2 imes g ea e han he numbe o connec ed cubic plana mul ig aphs wi h n e ices, which is
a con adic ion.
We p oceed as in he las pa o he p oo o Theo em 2. We compu e
C0=C(ρm)≈0.070660 and C5≈ −0.098979,
oge he wi h he singula expansion o G(x) = exp(C(x)), which is gi en by
G0+G2X2+G4X4+G5X5+O(X6),
whe e
G0≈1.073217 and G5≈ −0.106226.
Finally, an applica ion o Lemma 10 gi es he es ima es as claimed. As a co olla y, he p obabili y ha a
andom cubic plana mul ig aph is connec ed is pm=h0/h ≈0.931778.
Rema k. We p o ide he e a sho explana ion o he simila i y be ween equa ions (1) and (2). Le p1(x2)
be he polynomial in (1) and p2(x2) ha in (2). A e making he change o a iables y=x2,p1(y) and
p2(y) a e ob ained, by elimina ing, espec i ely, in he sys ems o equa ions
H1=1 + 1
2Ty(1 + D)32−(1 + D)2y2
4+ 1 −y(D−1)= 0, y(1 + D)3=τ,
H2=1 + 1
2Ty(1 + D)32−(1 + D)2y2
4+ 1 −y(D+ 3)= 0, y(1 + D)3=τ.
Now ew i e H1and H2as
H1=1 + 1
2Ty(1 + D)32−(1 + D)2y2
4+ 1−2y(1 + D)2−τ,
H2=1 + 1
2Ty(1 + D)32−(1 + D)2y2
4+ 1+ 2y(1 + D)2−τ.
We deduce om he e ha p2(y) = p1(−y), which is equi alen o he ela ion be ween (1) and (2).
18
3.5 P- ecu si e sequences
A se ies is D- ini e i i sa is ies a linea di e en ial equa ion wi h polynomial coe icien s. I is well-known
(see Chap e 6 in [15]) ha { n}is P- ecu si e i and only i P nxn/n! is D- ini e.
P oo o Theo em 5. We show ha in each case he co esponding gene a ing unc ions a e D- ini e.
Connec ed and 2-connec ed g aphs. The gene a ing unc ion C0(x) is algeb aic, hence i is D- ini e [15]. I
ollows ha C(x) is also D- ini e. The same a gumen applies o he gene a ing unc ion B(x) o 2-connec ed
g aphs.
A bi a y g aphs. We use he same a gumen as in [14], namely ha i C0(x) is algeb aic hen exp(C(x))
is D- ini e. Fo comple eness we b ie ly ecall he p oo . Le G(x) = eC(x). One shows by induc ion
ha G(i)=Ri(C0, x)G(x), whe e Riis a a ional unc ion in C0and x. Since C0is algeb aic, Q(C0, x)
is ini e dimensional o e Q(x), say o dimension k. Hence he e a e a ional unc ions Si(x) such ha
Pk
i=0 Si(x)Ri(C0, x)=0.I ollows ha
S0(x)G+S1(x)G0+···+Sk(x)G(k)= 0.
p o ing ha Gis D- ini e.
Mul ig aphs. In his case we canno apply he p e ious a gumen , since he e is no di ec ela ion
be ween he gene a ing unc ions D(x) and C0(x). I ollows om Equa ion (17) ha D(x) is algeb aic. We
use Equa ion (18) o exp ess G(x) = exp(C(x)) in e ms o D(x), and he ac ha he exponen ial o an
algeb aic unc ion is D- ini e, o ob ain
G(x) = eC(x)=J(x)eM(x,1+D),
whe e J(x) is a D- ini e unc ion (no ice ha he loga i hm in (18) cancels wi h he exponen ial). We nex
use he explici exp ession (9) and he ac ha U(z) is algeb aic o conclude ha exp(M(x, 1 + D)) is
D- ini e (again a loga i hm cancels). Since he p oduc o D- ini e unc ions is D- ini e, we conclude ha
G(x) is D- ini e.
4 P oo s o limi law esul s: iangles
In his sec ion we ob ain gene a ing unc ions encoding iangles in cubic plana g aphs and i s dis ibu ion
in andom cubic plana g aphs. The main idea behind hese p oo s is ha we a e able o en ich he ne wo k
decomposi ion o g aphs in o de o encode he numbe o iangles. Mo e p ecisely, in o de o s udy he
dis ibu ion o he numbe o iangles, we s a wi h 3-connec ed cubic plana g aphs. By duali y his
amoun s o s udying e ices o deg ee 3 in iangula ions. The la e p oblem is sol ed in Sec ion 4.1. We
hen use i o coun iangles in ne wo ks in Sec ion 4.2. In Sec ion 4.3 we pe o m he singula i y analysis
o he equa ions ob ained in Sec ion 4.2, and comple e he p oo o Theo em 7. Finally, as a byp oduc o
he p e ious ideas, in Sec ion 4.4 we apply hese ools o enume a e plana cubic iangle- ee g aphs. This
does no ollow di ec ly om Theo em 7 as one needs o adap he equa ions sa is ied by he associa ed
gene a ing unc ions and pe o m a delica e analysis o singula i ies.
4.1 Ve ices o deg ee 3 in iangula ions
In his sec ion we ob ain he gene a ing unc ion o iangula ions encoding he numbe o e ices o deg ee 3.
This will be done by en iching he classical decomposi ion by Tu e o iangula ions in e ms o 4-connec ed
iangula ions [16].
Th oughou his sec ion T∗deno es he class o iangula ions no educed o a iangle. The associa ed
gene a ing unc ion is T∗(z) = T(z)−z, whe e T(z) is as in Equa ion (4). Addi ionally z−1T∗(z) coun s
iangula ions (no educed o a iangle) in e ms o in e nal iangles. Recall ha T4(z) is he gene a ing
unc ion o 4-connec ed iangula ions, gi en in (7). In bo h cases, zencodes he numbe o e ices minus
19
wo. A iangula ion A∈ T ∗has a 4-connec ed co e C, ob ained by emo ing he e ices inside maximal
sepa a ing iangles; he co e is ei he a 4-connec ed iangula ion o is isomo phic o K4. Then Ais
ob ained by possibly eplacing he in e nal aces o Cwi h a bi a y iangula ions. This leads o he
ollowing equa ion, linking T∗(z) and T4(z):
T∗(z) =
T4z1 + z−1T∗(z)2
1 + z−1T∗(z)+z2(1 + z−1T∗(z))3.(19)
The i s e m in he igh hand-side is equi alen o Equa ion (2.6) om [16]; he second one co esponds
o he case when he co e is K4. No e ha he e we wan o eplace wi h iangula ions in T∗ins ead o T,
as eplacing a ace wi h a single iangle amoun s o doing no hing. This is al eady encoded by he e m 1
in 1 + z−1T∗(z).
Ou goal is o e ine (19) by coun ing e ices o deg ee 3. An in e nal e ex in a iangula ion is a
e ex no inciden wi h he oo ace, o he wise i is called ex e nal. Le (z, u) be he gene a ing unc ion o
iangula ions, whe e zis as be o e and uencodes in e nal e ices o deg ee 3. In pa icula , T∗(z) = (z, 1).
Le now T0be he se o iangula ions (excep K4) in which he deg ee o he oo e ex is equal o 3, and
T1 hose whe e he deg ee is g ea e han 3. Then we ha e T∗=T0∪T1∪{K4}. Le T0(z, u) and T1(z, u) be
he associa ed gene a ing unc ions, whe e unow coun s he o al numbe o e ices o deg ee 3, including
he ex e nal ones. Then we ha e
T∗(z, u) = T0(z, u) + T1(z, u) + z2u4.
In he nex lemma we ob ain exp essions o bo h T0(z, u) and T1(z, u):
Lemma 16. The gene a ing unc ion = (z, u)is de ined implici ly in e ms o T4(z)as
=
T4z1 + z−1 2
1 + z−1 +z2(1 + z−1 )3+u−1.(20)
In addi ion, we ha e
T1(z, u) = zu , (21)
T0(z, u) = (1 + 2zu −3z) −z2u. (22)
P oo . The i s equa ion ollows di ec ly om (19). The only di e ence comes om he second e m asso-
cia ed o K4: when none o he in e nal aces is eplaced wi h a iangula ion, he cen al e ex has deg ee
3 and he con igu a ion is encoded as u.
When emo ing he oo e ex (and he h ee adjacen edges) o a iangula ion in T1, we ob ain a
smalle iangula ion. The e e se ope a ion is o ake a iangula ion, d aw a e ex on i s oo ace, join
i wi h he h ee e ices on he ex e nal ace, and e- oo he esul ing map. This gi es (21).
In o de o ob ain T0we i s compu e T(z, u). The ollowing equa ion ollows om (20) by analyzing
again he case whe e he co e is K4, and aking in o accoun how many in e nal aces a e eplaced wi h
iangula ions:
T∗(z, u) =
T4z1 + z−1 2
1 + z−1 +z2(1 + z−1 )3−1−3z−1 + 3uz−1 +u4.
Finally, we use T∗(z, u) = T0(z, u) + T1(z, u) + z2u4, and a e a simple compu a ion we ge (22).
4.2 T iangles in ne wo ks
We a e now back o labeled g aphs and exponen ial gene a ing unc ions. In his sec ion he goal is o
ob ain equa ions o ne wo ks encoding also iangles. He e, a iable xma ks e ices and uma ks iangles.
20
Di(x, u) is he gene a ing unc ion o non-is hmus ne wo ks in which he oo edge belongs o exac ly
i∈ {0,1,2} iangles. (obse e ha in a cubic g aph he e is no o he possibili y). The same con en ion
applies o se ies, pa allel and h-ne wo ks. The special case when he 3-connec ed co e o an h-ne wo k is
K4is encoded in he gene a ing unc ions Wi. We le E(x, u) be he gene a ing unc ion o ne wo ks whe e
iangles inciden o he oo edge a e no coun ed, ha is,
E(x, u) = D0+u−1D1+u−2D2.
The nex wo lemmas p o ide he exp essions o he se ies Di,Si,Pi,Wi,I,Land o H0, H1(H0, H1will
be ea ed sepa a ely as hey a e echnically mo e in ol ed).
Lemma 17. The ollowing equa ions hold:
D0=S0+P0+W0+L+H0,
D1=S1+P1+W1+H1,
D2=P2+W2,
I=L2
x2,
L=1
2x2(I+E−L) + 1
2x2(u−1) x2(E−L) + ux2L+L2),
P0=x2(E−L) + 1
2x2(E−L)2,
P1=ux2L(E−L) + u2x2L,
P2=1
2u2x2L2,
S0=EE−(S0+u−1S1)−u−1S1,
S1=uL3+ 2ux2L(E−L)+2u2x2L2,
W0=1
2x42(1 + u)E2+ 8E3+ 5E4+E5,
W1=1
2x44u2E+ 6uE2+ 2uE3,
W2=1
2x4u4+u2E.
P oo . Equa ions o D0, D1and D2a e clea , since S2=P2=H2= 0. The equa ion o Iis he same
as in he uni a ia e case. The equa ion o Lis ob ained as ollows: om he main e m x2
2(I+E−L)
we need o conside sepa a ely h ee si ua ions in which a new iangle is c ea ed: hey a e illus a ed in
Figu e 5. The co esponding gene a ing unc ions a e 1
2ux4(E−L), 1
2u2x4Land 1
2ux2L2, hence he e m
x2
2(u−1) x2(E−L) + x2
2uL +1
2L2.
E−L
L
Figu e 5: The h ee con igu a ions in Lwhe e an ex a iangle is c ea ed. The associa ed gene a ing
unc ions a e espec i ely 1
2x4u(E−L), 1
2x4u2Land 1
2x2uL2.
In he case o pa allel ne wo ks, when using ne wo ks in Lwe c ea e iangles inciden wi h he oo edge
o he ne wo k. The possible cases in P1and P2a e illus a ed in Figu e 6.
21

E−L
L
LL
Figu e 6: Con ibu ions o ux2L(E−L) o P1and 1
2x2u2L2 o P2.
The equa ion o S1 ollows by conside ing he possible cases in which he oo edge is inciden wi h a
iangles, as desc ibed in Figu e 7.
L
L
L
L
E−L
L
L
Figu e 7: Con ibu ions o S1: he co esponding gene a ing unc ions a e uL3,ux2L(E−L), u2x2L2. Fo
he second and hi d con igu a ion he e a e wo possibili ies.
The equa ion o S0is ob ained as in he uni a ia e case, by sub ac ing he e m u−1S1. Finally, he
equa ions o W0, W1and W2a e ob ained by conside ing all cases whe e K4is he co e o he h-ne wo k.
Obse e ha he di e en coe icien s ha appea in he exp essions o W0,W1and W2a e due o symme ies
o K4.
The p e ious sys em can be easily ew i en as we ha e done ea lie (see he pa ag aph a e he s a emen
o Lemma 13) so ha he igh -hand e ms ha e non-nega i e coe icien s, and hus admi s a unique non-
nega i e powe se ies as solu ion. The ollowing lemma gi es he exp ession o H0and H1in e ms o T0(z)
and T1(z). Join wi h he p e ious lemma, his comple es he sys em o equa ions encoding iangles:
Lemma 18. Le (x, u)be he gene a ing unc ion de ined by Equa ion (20). Then H0and H1a e gi en by
he ollowing exp essions:
H1(x, u) = 1
2x2u· x2(1 + E)3,1 + u−1
(1 + E)3,
H0(x, u) = 1
2 x2(1 + E)3,1 + u−1
(1 + E)31−x2(E−2u+ 3)
1 + E−1
2x4(1 + E)2((1 + E)3+u−1)).
P oo . We say ha a iangle in a ne wo k is ex e nal i i is inciden wi h he oo edge. The edges o an
ex e nal iangle ha a e no he oo edge a e called special.
We deno e by M0and M1 he amily o edge- oo ed 3-connec ed cubic plana g aphs (excep K4)
wi hou ex e nal iangles and wi h one ex e nal iangle, espec i ely, and le M0(x, y, u), M1(x, y, u) be he
22
associa ed gene a ing unc ions, whe e x,yand uma k e ices, edges and iangles, espec i ely. Simila ly
o Equa ion (8) we ha e ha
M0(x, y, u) = 1
2T0(x2y3, u), M1(x, y, u) = 1
2T1(x2y3, u).
Le m1(x, y, u) = M1(x, y, u)/(uy3), whe e now ucoun s non-ex e nal iangles, and ycoun s he numbe o
edges minus h ee (we do no coun he oo edge and he special edges).
A ne wo k in H1is ob ained om a g aph Gin M1in which we eplace edges (excep he oo edge)
wi h ne wo ks, and whe e he h ee edges o he ex e nal iangle o Ga e no eplaced ( ecall ha he
ex e nal iangle is he only iangle inciden wi h he oo edge). Obse e ha iangles in Ga e isola ed
(because Gis 3-connec ed), hence he e a e no iangles sha ing edges and he p e ious eplacemen can be
made. In pa icula , he e m u+ 3E+ 3E2+E3= (1 + E)3+u−1 encodes he subs i u ion o ne wo ks on
3-se s o edges de ining iangles (excep he ex e nal iangle and he co esponding edges, which a e no
subs i u ed). This ansla es in o he equa ion
H1(x, u) = u·m1x, 1 + E, 1 + u−1
(1 + E)3.
The exp ession o H1is ob ained by w i ing i s m1in e ms o T1, and hen w i ing T1in e ms o
using (21).
Le us now conside a ne wo k in H0. I can be ob ained in wo di e en ways: ei he om a co e wi hou
an ex e nal iangle, o om a co e wi h an ex e nal iangle in which some special edges a e eplaced wi h
a non-emp y ne wo k. Using a simila encoding a gumen as be o e we a i e a
H0(x, u) =
M0x, 1 + E, 1 + u−1
(1 + E)3
1 + E+ (2E+E2)·m1x, 1 + E, 1 + u−1
(1 + E)3,
whe e he ac o 2E+E2in he second summand co esponds o he subs i u ion o ne wo ks on he pai
o special edges. Using he exp essions o M0and m1in e ms o T0and T1, and Equa ions (21) and (22),
a e simpli ica ion we ge he exp ession o H0, as claimed.
We conclude his sec ion by exp essing he gene a ing unc ion o e ex- oo ed g aphs C•(x, u), whe e
xma ks e ices and uma ks iangles, in e ms o ne wo ks:
3C•(x, u) = D0+D1+D2+I−L−x2(D0+D1+D2)−L2.(23)
This equa ion is ob ained by conside ing all ne wo ks (which is coun ed by D0+D1+D2+I) and emo ing
hose whe e he oo edge is ei he a loop o a mul iple edge ( e m L+x2(D0+D1+D2) + L2). This
di e ence is equal o he gene a ing unc ion o ne wo ks wi h only simple edges, which by double coun ing
i is equal o 3C•(x, u).
4.3 Singula i y analysis and p oo o he main esul
A e ob aining he sys em o equa ions in Lemmas 17, 18 and Equa ion (23) we p oceed o analyze i . In
o de o apply Lemma 11 o p o ing a Gaussian limi law, ou i s ask is o ind he dominan singula i ies
(o xas a unc ion o u, o uclose o 1) o he unc ion C(x, u) coun ing iangles in connec ed cubic plana
g aphs. We s a inding he singula i ies o 3-connec ed g aphs. La e , we use he esul s om he p e ious
sec ion o ob ain he singula i ies o C(x, u).
Singula i ies o 3-connec ed g aphs. Recall ha he gene a ing unc ion (z, u) encodes iangula ions,
whe e zis he numbe o e ices minus 2 uencodes in e nal e ices o deg ee 3. I s exp ession in e ms o
T4(z) is gi en in Lemma 16. The nex esul gi es he dominan singula i ies o he gene a ing unc ion o
3-connec ed g aphs:
23
Lemma 19. Le (z, u)be as in Lemma 16. Le ube a ixed complex numbe wi h |u−1|< ε, whe e ε > 0
is su icien ly small. Then he poin z0=z0(u)whe e (z, u)ceases o be analy ic is he solu ion o he
ollowing equa ion:
z0(1 + (u−1)z0)2=27
256.(24)
Mo eo e , a he c i ical poin (z0, u)we ha e he ela ion:
(z0(u−1) + 1) (z0, u) = 1
8−z0(1 + (u−1)z0).(25)
P oo . The unique singula i y o T4(z) is a 4/27 (see Sec ion 2). Hence, o uin a small neighbo hood o
1, he only possible sou ce o singula i ies o (z, u) in Equa ion (20) comes om he singula i y o T4(z),
gi ing he ela ion
z0(1 + z−1
0 (z0, u))2= 4/27.
We also know ha T4(4/27) = 7/5832, hence a he singula poin we ha e
(z0, u) = 7/5832
1 + z−1
0 (z0, u)+z2
0((1 + z−1
0 (z0, u))3+u−1).
Elimina ing (z0, u) om he p e ious wo equa ions gi es (24), and an elemen a y compu a ion gi es Equa-
ion (25).
Singua i ies o connec ed g aphs. We ha e seen in he p oo o Theo em 1 ha he singula i ies o he
gene a ing unc ion D(x) o cubic ne wo ks come om he singula i ies o T(z). Va iable uma ks iangles,
which is a linea pa ame e . Hence, by con inui y and o usu icien ly close o 1, his also holds o he
bi a ia e gene a ing unc ions o ne wo ks. Fo a gi en uclose o 1, we le ρ(u) be he dominan singula i y
o he unc ion E(x, u). No ice ha , because o (23), i is also ha o C(x, u); he e is no cancella ion
because he e is none o u= 1. Rema k also ha ρ(1) is equal o he cons an ρ≈0.3192246062 om
Theo em 1.
In o de o de e mine ρ(u), we ind wo equa ions sa is ied by u,ρ(u) and E(ρ(u), u). Then elimina ing
Ewill gi e us ρ(u) implici ly in e ms o u. Once we ha e access o ρ(u), an applica ion o Lemma 11 will
gi e he asymp o ic no mal law wi h he co esponding momen s.
Lemma 20. Fo ixed uclose o 1, E(x, u)admi s wo dominan singula i ies gi en by he wo cu es ±ρ(u)
and such ha ρ(1) = ρ. As x→ρ(u)−, we ha e locally
E(x, u) = E0(u) + E2(u)1−x
ρ(u)+E3(u)1−x
ρ(u)3/2
+. . . ,
whe e E0(u),E2(u)and E3(u)a e analy ic unc ions.
Le x=ρ(u)be he posi i e dominan singula i y o E(x, u)and le E=E(x, u). Then he ollowing wo
equa ions hold:
x2(1 + E)31+(u−1)x22=27
256,(26)
256(1 + (u−1)x2)2(1 + E)A= 256x2(1 + (u−1)x2)3(E3+ 3E2+ 3E) + B, (27)
whe e
A=(u2x4−2ux4+x4−x2−2)2−4x2(1 + (u−1)x2)2E1/2,
B= 256(u−1)3x8+ 768(u−1)2x6+ 192(u−1)(3u+ 1)x4+ (1066u−810)x2+ 517.
24
P oo . Simila ly o he uni a ia e case, we show ha he only sou ce o singula i ies o E=E(x, u) comes
om = (x2(1 + E)3,1+(u−1)/(1 + E)3). Fu he mo e, he singula beha iou o ans e s di ec ly
o ha o E. In ou case, bo h s a emen s can be deduced di ec ly om a sligh ly modi ied e sion o
[4, Theo em 2.31], in which we now equi e ha |PE( (τ), E(ρ), ρ, 1)| 6= 0 when u= 1, and ha (z, u)
admi s a 3/2 singula beha iou locally a ound u= 1 and z=τ(u), whe e he τ(u) is he solu ion o
z0in (24). By elimina ion om he equa ions in Lemmas 17 and 18, we ob ain a polynomial equa ion
P( , E, x, u) = 0, which has deg ee 6 in E(i is oo big o be displayed he e). F om he e, we check ha
|PE( (τ), E(ρ), ρ, 1)| ≈ 7.1818705965. Fo he second condi ion, we elimina e V(z) and T4(z) om (7), (20)
and z=V(z)(1 −V(z))2 o ob ain an i educible polynomial equa ion Q( (z, u), z, u) = 0. Using New on’s
polygon algo i hm on Q(as i is squa e- ee), we compu e he Puiseux expansion o (z, u) locally a ound
z=τ(u), which is o he o m:
(z, u) = 0(u) + 2(u)1−z
τ(u)+ 3(u)1−z
τ(u)3/2
+. . . ,
whe e 0(u), 2(u) and 3(u) a e analy ic unc ions.
Le us inally conside he exp essions o H0and H1in Lemma 18. Since he singula i ies o Emus
come om he subs i u ion in (z, u), he poin (z1, u1) = (x2(1 + E)3,1 + (u−1)/(1 + E)3) mus be a
singula poin o (z, u). The singula i ies o (z, u) a e gi en by he ela ion (24), hence we ha e:
z1(1 + (u1−1)z1)2=x2(1 + E)31 + 1 + (u−1)
(1 + E)3−1x2(1 + E)32
=27
256,(28)
which is p ecisely (26). Le us now deduce Equa ion (27). We i s need he e alua ion o (z, u) a he poin
(z1, u1). This ollows di ec ly om (25) and (26) and gi es:
(z1, u1) = 32(u−1)x2+ 5
256(1 + (u−1)x2)2.
No ice ha all he unc ions, in ol ed in bo h Lemmas 17 and 18, can be w i en in e ms o E, L and he
a iables xand u. Sol ing o Land subs i u ing p o ides a second equa ion on E,x, and u. The solu ion
o Lis gi en by:
L(x, u) = x2+ 2 −(u−1)2x4−A
2(1 + (u−1)x2),(29)
whe e Ais an in he s a emen . I emains inally o w i e D0,D1,D2in e ms o E,L,xand u, hen o
eplace Lwi h he exp ession in (29), and o pe o m an elemen a y compu a ion o ob ain (27).
P oo o Theo em 7. One can elimina e E om he sys em composed o Equa ions (26) and (27) o
ob ain a single polynomial equa ion p(x, u) = 0 in xand u, whose smalles posi i e solu ion in xis he
singula i y ρ(u) o E(x, u). The polynomial phas deg ee 40 in x2and is oo la ge o be displayed he e. We
hen di e en ia e p(ρ(u), u) wi h espec o uand compu e he ollowing alues (using Maple):
ρ0(1) = −0.0389371919, ρ00(1) = 0.0229417852.
Al e na i ely, we can di e en ia e (26) and (27) and sol e he co esponding sys em in ol ing ρ(1) and ρ0(1),
and simila ly o ρ00(1).
In o de o apply Lemma 11, we need o show ha E(x, u) is analy ic in a ∆-domain a x=ρ(u).
By Lemma 20, E(x, u) has an expansion in powe s o p1−x/ρ(u) o unea 1. I is hence analy ic in a
su icien ly small neighbo hood o ρ(u) sliced along he ay [ρ(u),∞]. Conside now uin a small neighbo hood
Uo 1, and ake u0∈U eal wi h ρ(u0)>|ρ(u)|. By he same a gumen as in he p oo o he uni a ia e
case (Theo em 1), E(x, u) is analy ic in a ∆-domain a u0. I ollows ha E(x, u) is analy ic in a ∆-domain
a ρ(u). Thus, o uin a small neighbo hood o 1, we ge he es ima e
[xn]E(x, u) = c(u)·n−5/2ρ(u)−n1 + O(n−1).
By a di ec applica ion o Lemma 11, we a e able o i s compu e he alues ρ0(1) and ρ00(1), hen he alues
o µand λ, as claimed. This concludes he p oo o Theo em 7.
25