# The Higgs Field and the Jordan Brans Dicke Cosmology

Onder<EMAIL_ADDRESS>Levent
<EMAIL_ADDRESS>Metin<EMAIL_ADDRESS>Yelda
<EMAIL_ADDRESS>
Selale<EMAIL_ADDRESS>and Tarik<EMAIL_ADDRESS>
Department of Physics, Bogazici University, Bebek, Istanbul, Turkey

###### Abstract

We investigate a field theoretical approach to the Jordan-Brans- Dicke (JBD)
theory extended with a particular potential term on a cosmological background
by starting with the motivation that the Higgs field and the scale factor of
the universe are related. Based on this relation, it is possible to come up
with mathematically equivalent but two different interpretations. From one
point of view while the universe is static, the masses of the elementary
particles change with time. The other one, which we stick with throughout the
manuscript, is that while the universe is expanding, particle masses are
constant. Thus, a coupled Lagrangian density of the JBD field and the scale
factor (the Higgs field), which exhibit a massive particle and a linearly
expanding space in zeroth order respectively, is obtained. By performing a
coordinate transformation in the field space for the reduced JBD action whose
kinetic part is nonlinear sigma model, the Lagrangian of two scalar fields can
be written as uncoupled for the Higgs mechanism. After this transformation, as
a result of spontaneous symmetry breaking, the time dependent vacuum
expectation value (vev) of the Higgs field and the Higgs bosons which are the
particles corresponding to quantized oscillation modes about the vacuum, are
found.

##  1 Introduction

The concept of mass has been very important and challenging to understand at
the fundamental level throughout the advancement of modern physics. The
particle physics as well as the foundations of classical physics such as the
dynamics of particle motion and the phenomenon of gravitation, in fact depend
on this concept. Lately by the discovery of the Higgs boson[1], one of the
most striking developments in our understanding of this concept has been the
fact that the mass in physics is fundamentally resulting from the vacuum
expectation value of the Higgs field[2]. Also, all the elementary particles in
the standard model obtain their masses by this mechanism[3][4][5] which is
only consistent in Minkowski spacetime. Although from a historical perspective
the concept is divided into two as inertial and gravitational masses, their
equivalence which is known the weak equivalence principle (WEP), is essential
by experiments[6]. WEP ensures test bodies follow the same path in a
gravitational field regardless of their compositions. So, this equivalence was
one of the main motivations for Einstein to construct the general theory of
relativity which explains the gravitation in a purely geometrical way. Another
motivation was Mach’s principle which relates an inertial force on a body to
the gravitational effects originating from the matter distribution of the
universe. While Newton’s concept of absolute space defines a special frame of
reference and an inertial force is the result of motion relative to this
frame, Mach’s principle states that the observable motion is the relative one
and there is no a special frame of reference. Thus, based upon Mach’s
principle, a test particle experiences an inertial force because of its
relative motion to the rest of the universe, or simply, the physical space
shaped by distant stars and galaxies. Furthermore, a model which relates
inertia to the gravitational potential of the universe, has been proposed by
Sciama[7]. In the rest of this section, a novel connection between inertial
mass and the metric tensor is constructed by means of the Higgs field. A
similar model[8] has recently been introduced by two of the authors and the
more complete and the precise one in terms of theoretical arguments and
calculations is studied in this manuscript.

In the general theory of relativity, motion of particles are determined by the
action

$S=-m\int ds=-m\int\sqrt{g_{\mu\nu}dx^{\mu}dx^{\nu}},$ (1)

where $m$ and $ds$ are the mass of the particle and the length of the
Riemannian line element respectively. As is stated earlier, since, from a
field theoretical point of view, a particle is gained mass because of its
interaction with Higgs field $\phi$, the mass of the particle should be time
dependent if the vev of the Higgs field changes with time throughout the
evolution of the universe. However, the variation of the field must be at a
sufficiently slow rate so that the concept of mass is not put under too much
stress and the factor in front of the interaction term is interpreted as mass
in a field theoretical Lagrangian density. So, once the solution of the Higgs
field is obtained in terms of the parameters of our model, it will be shown
that this condition is satisfied. Based on this motivation, the same action in
Eq.(1) can be written as

$S=-m_{0}\int\frac{\phi(t)}{\phi_{0}}\sqrt{g_{\mu\nu}dx^{\mu}dx^{\nu}}.$ (2)

Another fundamental understanding of the universe is the concept of the
expanding universe as described by the FLRW metric tensor[9, 10, 11, 12] for
which the line element is given by

$ds^{2}=a^{2}(t)(-dt^{2}+dx^{2}+dy^{2}+dz^{2})$ (3)

where t is, in cosmological language, called conformal time. Here and
henceforth we will use units $\hbar=c=1$. If the mass is determined by the
time dependent cosmological expectation value of the Higgs field, for a
macroscopic theory one can use Eq.(2) to embed the factor $\phi(t)/\phi_{0}$
into the metric and the line element becomes

$ds^{2}=<\phi(t)/\phi_{0}>^{2}\eta_{\mu\nu}dx^{\mu}dx^{\nu}$ (4)

as far as homogeneous and isotropic space-time is considered. Now, while
$\phi/\phi_{0}$ is representing the time dependence of the mass, from another
perspective, it can be considered as a part of the metric tensor for a
cosmological scenario by the relation

$a(t)=<\phi(t)/\phi_{0}>.$ (5)

Thus, roughly speaking, the scale factor $a$ must be related to the time
dependent cosmological expectation value of the Higgs field.

Besides many successes of the general theory of relativity in explaining some
phenomena in the solar system as well as in the standard model of cosmology
such as the precession of the mercury, gravitational lensing, proton-neutron
ratio in the early universe and the primordial nucleosynthesis, its
insufficiency to solve the late-time accelerating expansion of the universe
and the galaxy rotation curves without adding dark energy and dark matter as
unknown exotic constituents led to search for the modified or the alternative
gravity theories[13][14]. It also suffers from some conceptual issues[15][16]
related to Mach’s principle which it relies on. Whereas modified gravity
theories satisfy WEP, the strong equivalence principle (SEP) is violated as a
result of the introduction of a fifth force[15][17]. Thus, objects which have
different gravitational binding energies, move on different geodesics of the
space-time metric. In this sense, the general theory of relativity is the only
tensor theory which satisfies both WEP and SEP. Among modified gravity
theories, due to the coupling of a simple scalar field to the geometry of
space-time, scalar-tensor theories are the more prevalent and flexible
alternatives. In this manuscript, we will consider the Jordan Brans Dicke
(JBD) theory[15, 18, 19, 20] which is the first scalar-tensor theory and seems
to be a more complete theory of gravitation with respect to Mach’s principle.
Furthermore, for our case, it is more suitable to show the relation between
the relativistic cosmology and the Higgs mechanism by relating the scalar
fields of two picture. In their original paper, Brans and Dicke define the
reciprocal of Newton’s constant $1/G$ as the scalar field which has the
dimension of mass squared. Since our approach will mostly be field
theoretical, it is better define a field to have the dimension of mass. Thus,
the JBD action extended with a potential term (here, a massless JBD field is
taken into account) turns out to be

$S=\int
d^{4}x\sqrt{-g}\left(-\frac{\tilde{\xi}^{2}}{2}\tilde{\chi}^{2}R-\frac{1}{2}g^{\mu\nu}\partial_{\mu}\tilde{\chi}\partial_{\nu}\tilde{\chi}-\frac{\tilde{\lambda}}{4}\tilde{\chi}^{4}\right).$
(6)

Here, $R$, $\tilde{\chi}$ and $\tilde{\xi}^{2}$ are the Ricci scalar, the JBD
scalar field and the dimensionless parameter respectively. As it will be
explained at the beginning of the next section, the use of tilde sign in
Eq.(6) is because of some dimensional concerns for coordinate transformation
in field space. Furthermore, although the coupling parameter $\omega$ which is
the original JBD parameter, is more common in the literature, we prefer to
stick with the action form in Eq.(6). So, the relation between two parameters
is given by $\tilde{\xi}^{2}=-1/4\omega$.

##  2 The Higgs Field and the Conformal Factor in the JBD Theory

Since it is better fit this scalar-tensor theory into relatively simpler form
as the Lagrangian of two scalar field in Minkowski spacetime, we use the
following two relations

$\sqrt{-g}=a^{4}(t)\sqrt{-\eta}=a^{4}(t)$ (7)
$R=6\frac{\partial_{0}^{2}a}{a^{3}}$ (8)

to write the Lagrangian density in Eq.(6) in terms of dimensionless scalar
fields $\chi$ and $a$ as

$\mathcal{L}=-\frac{\xi^{2}}{2}\chi^{2}a\partial_{0}^{2}a+\frac{\mu^{2}}{2}a^{2}(\partial_{0}\chi)^{2}-\frac{\lambda}{4}a^{4}\chi^{4}$
(9)

where $\chi=\tilde{\chi}/\mu$ and it has undergone dimensional transmutation.
To make $\chi$ dimensionless, $\mu$ must have dimension of mass and so
dimensionful constants are defined as $\xi=\mu\tilde{\xi}$ and
$\lambda=\mu^{4}\tilde{\lambda}$. Also, the factor of six in the Ricci scalar
has already been embedded within $\xi^{2}$.

After the first term in Eq.(9) is expanded by applying integration by parts,
the Lagrangian density becomes

$\mathcal{L}=-\frac{\xi^{2}}{2}[\partial_{0}(\chi^{2}a\partial_{0}a)-2a\chi\partial_{0}a\partial_{0}\chi-\chi^{2}(\partial_{0}a)^{2}]+\frac{\mu^{2}}{2}a^{2}(\partial_{0}\chi)^{2}-\frac{\lambda}{4}a^{4}\chi^{4}.$
(10)

At this point, since the first term in the square bracket is a total
divergence, it can be set to zero at the infinity in the action. So, after
disregarding this term, by addition and subtraction of the term
$\frac{\xi^{2}}{2}a^{2}(\partial_{0}\chi)^{2}$ into the Lagrangian density,
and then taking the factor of $a^{2}\chi^{2}$ outside the parenthesis, one
ends up with

$\mathcal{L}=\frac{\xi^{2}}{2}a^{2}\chi^{2}\left[\left(\frac{\partial_{0}\chi}{\chi}\right)^{2}+2\frac{\partial_{0}a}{a}\frac{\partial_{0}\chi}{\chi}+\left(\frac{\partial_{0}a}{a}\right)^{2}\right]+\frac{\mu^{2}-\xi^{2}}{2}a^{2}(\partial_{0}\chi)^{2}-\frac{\lambda}{4}a^{4}\chi^{4}.$
(11)

The plus sign in front of the bracket in which the terms correspond the
kinetic energy, implies the positivity of $\xi^{2}$ but negativity of the JBD
parameter $\omega$ based upon our definition in the introduction. In order to
simplify this expression, the following relation for the terms inside the
bracket and the definitions (or the coordinate transformations in the field
space) for fields $\alpha$ and $\gamma$ are very useful.

$[\partial_{0}(\ln\chi+\ln a)]^{2}=[\partial_{0}(\ln\chi
a)]^{2}=[\partial_{0}\ln\alpha]^{2}$ (12) $\alpha=\chi a$ (13)
$\gamma=\ln\chi$ (14)

Then, the Lagrangian density can be put in the form

$\mathcal{L}=\frac{\xi^{2}}{2}(\partial_{0}\alpha)^{2}+\frac{\mu^{2}-\xi^{2}}{2}\alpha^{2}(\partial_{0}\gamma)^{2}-\frac{\lambda}{4}\alpha^{4}.$
(15)

Based upon the equation of motion of $\gamma$, since

$\frac{\partial\mathcal{L}}{\partial\gamma}=0,$ (16)
$\frac{\partial\mathcal{L}}{\partial(\partial_{0}\gamma)}=(\mu^{2}-\xi^{2})\alpha^{2}\partial_{0}\gamma$
(17)

must be equal to a constant. Thus,

$\partial_{0}\gamma=\frac{C}{(\mu^{2}-\xi^{2})\alpha^{2}}.$ (18)

After some algebra, Hamiltonian density is found as

$\mathcal{H}=\frac{\xi^{2}}{2}(\partial_{0}\alpha)^{2}+\frac{\mu^{2}-\xi^{2}}{2}\alpha^{2}(\partial_{0}\gamma)^{2}+\frac{\lambda}{4}\alpha^{4},$
(19)

and using Eq.(18) in Eq.(19) yields

$\mathcal{H}=\frac{\xi^{2}}{2}(\partial_{0}\alpha)^{2}+\frac{C^{2}}{2(\mu^{2}-\xi^{2})}\frac{1}{\alpha^{2}}+\frac{\lambda}{4}\alpha^{4}.$
(20)

Before obtaining the equation of motion of $\alpha$, one must have the
Hamiltonian density in terms of the field and its canonical momentum. In our
case, it will be equal to

$\mathcal{H}=\frac{1}{2\xi^{2}}\pi_{\alpha}^{2}+\frac{C^{2}}{2(\mu^{2}-\xi^{2})}\frac{1}{\alpha^{2}}+\frac{\lambda}{4}\alpha^{4},$
(21)

where the canonical momentum is

$\pi_{\alpha}=\xi^{2}\partial_{0}\alpha.$ (22)

Furthermore, since the equation of motion is given by

$-\frac{\partial\mathcal{H}}{\partial\alpha}=\partial_{0}\pi_{\alpha},$ (23)

and the left hand side of Eq.(23) is

$-\frac{\partial\mathcal{H}}{\partial\alpha}=\frac{C^{2}}{(\mu^{2}-\xi^{2})}\frac{1}{\alpha^{3}}-\lambda\alpha^{3},$
(24)

after some algebraic manipulation one can easily get the equation of motion as

$\partial_{0}^{2}\alpha-\frac{C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\frac{1}{\alpha^{3}}+\frac{\lambda}{\xi^{2}}\alpha^{3}=0.$
(25)

In Eq.(21), last two terms behave as an effective potential, so one may write

$\mathcal{H}=\frac{\xi^{2}}{2}(\partial_{0}\alpha)^{2}+V_{eff},$ (26)

where

$V_{eff}=\frac{C^{2}}{2(\mu^{2}-\xi^{2})}\frac{1}{\alpha^{2}}+\frac{\lambda}{4}\alpha^{4}.$
(27)

To determine the vacuum expectation value of the field, the derivative of the
potential with respect to $\alpha$ must be equal to zero

$\frac{\partial V_{eff}}{\partial\alpha}=0.$ (28)

This simple procedure gives the vev of $\alpha$

$\alpha_{0}=\left(\frac{C^{2}}{\lambda(\mu^{2}-\xi^{2})}\right)^{1/6}.$ (29)

After substituting Eq.(29) in Eq.(18) in order to solve the field $\gamma$ at
the vacuum

$\partial_{0}\gamma=\frac{C}{(\mu^{2}-\xi^{2})\alpha_{0}^{2}}=\left(\frac{\lambda
C}{(\mu^{2}-\xi^{2})^{2}}\right)^{1/3}=D,$ (30)

$\gamma$ is found

$\gamma=\ln\chi=Dt+E,$ (31)

where $D$ and $E$ are another constants which must be determined. Then, on the
basis of the definition in Eq.(14), the JBD scalar field, is obtained at the
vacuum as

$\chi=e^{Dt+E}.$ (32)

Since the temporal evolution of the universe is designated by the scale factor
which also gives the time dependence of the Higgs field in our theoretical
model, we can take advantage of the definition of $\alpha$ at its vev

$\alpha_{0}=a\chi,$ (33)

to find

$a=\frac{\alpha_{0}}{e^{Dt+E}}=\exp[-D(t-t_{0})],$ (34)

where

$\alpha_{0}e^{-E}=e^{Dt_{0}},$ (35)

in which $t_{0}$ is the age of the universe to make the scale factor equal to
one today. As it is seen, Eq.(35) implies an exponential expansion for space-
time intervals but this is true in comoving time. After one switches to the
cosmological time which will be represented with $t^{\prime}$ throughout the
manuscript, and arrange constants accordingly to be able to set today’s value
of $a$ to one, a linear expansion is obtained

$a(t^{\prime})=\frac{t^{\prime}}{t_{0}^{\prime}}.$ (36)

We have already learned the evolution of the fields with time at the vev of
$\alpha$. Now, a small perturbation can be added to $\alpha$

$\alpha=\alpha_{0}(1+\epsilon(t)),$ (37)

and insert this into Eq.(25) to get

$\partial_{0}^{2}\epsilon(t)-\frac{C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\alpha_{0}^{-4}(1+\epsilon(t))^{-3}+\frac{\lambda}{\xi^{2}}\alpha_{0}^{2}(1+\epsilon(t))^{3}=0.$
(38)

Since the perturbation is small in comparison with $\alpha_{0}$, the second
and the third terms in Eq.(38) can be expanded by keeping only the zeroth and
the first order terms and it turns out to be

$\partial_{0}^{2}\epsilon(t)-\frac{C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\alpha_{0}^{-4}(1-3\epsilon(t))+\frac{\lambda}{\xi^{2}}\alpha_{0}^{2}(1+3\epsilon(t))=0.$
(39)

Since the zeroth order terms give

$-\frac{C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\alpha_{0}^{-4}+\frac{\lambda}{\xi^{2}}\alpha_{0}^{2}=0,$
(40)

we are left with the equation to solve

$\partial_{0}^{2}\epsilon(t)+\left(\frac{3C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\alpha_{0}^{-4}+\frac{3\lambda}{\xi^{2}}\alpha_{0}^{2}\right)\epsilon(t)=0.$
(41)

The constant term in the parenthesis has the dimension of mass squared so it
may be redefined to write the equation as

$\partial_{0}^{2}\epsilon(t)+m^{2}\epsilon(t)=0,$ (42)

where

$m^{2}=\left(\frac{3C^{2}}{\xi^{2}(\mu^{2}-\xi^{2})}\alpha_{0}^{-4}+\frac{3\lambda}{\xi^{2}}\alpha_{0}^{2}\right).$
(43)

Using the vev of $\alpha$ from Eq.(29) makes $m^{2}$ to be equal to

$m^{2}=\frac{6(\lambda C)^{2/3}}{\xi^{2}(\mu^{2}-\xi^{2})^{1/3}},$ (44)

then the solutions for $\epsilon$ and $\alpha$, around the vacuum, are found
as

$\epsilon(t)=\epsilon_{0}(e^{imt}+e^{-imt}),$ (45)
$\alpha=\alpha_{0}(1+\epsilon_{0}(e^{imt}+e^{-imt})).$ (46)

Ultimately, we are interested in the solutions of the fields $\chi$ and $a$.
We can follow the same procedure as before by finding $\gamma$ first, then
$\chi$ and $a$. To do that Eq.(46) is placed into Eq.(18) again by ignoring
second and higher order terms of $\zeta$

$\partial_{0}\gamma=\frac{C}{(\mu^{2}-\xi^{2})\alpha^{2}}=\frac{C}{(\mu^{2}-\xi^{2})}\alpha_{0}^{-2}\left(1-2\epsilon(t)\right),$
(47)

then by using the definition of constant $D$ and integrating

$\partial_{0}\gamma=D(1-2\epsilon(t)),$ (48)

$\gamma$ is gained as

$\gamma=Dt+F+\frac{i2D}{m}\epsilon_{0}(e^{imt}-e^{-imt}).$ (49)

Here, $F$ is another integration constant which must be defined. Using the
relations $\gamma=\ln\chi$ and $\alpha=a\chi$ one more time in order results
in

$\chi(t)=\exp\left(Dt+F+\frac{i2D}{m}\epsilon_{0}(e^{imt}-e^{-imt})\right),$
(50)
$a(t)=\alpha_{0}(1+\epsilon(t))\exp\left(-Dt-F-\frac{i2D}{m}\epsilon_{0}(e^{imt}-e^{-imt})\right).$
(51)

Once again the higher order terms are disregarded because of the fact that
$\epsilon\ll 1$ and constant $F$ is selected to be equal to $E$ in Eq.(31)
(since $a(t_{0})=1$), so the evolution of the universe in the conformal time
is

$a(t)=\exp\left(-D(t-t_{0})+\epsilon_{0}\left(\left(1-\frac{i2D}{m}\right)e^{imt}+\left(1+\frac{i2D}{m}\right)e^{-imt}\right)\right),$
(52)

and in the cosmological time is

$a(t^{\prime})=\left(\frac{t^{\prime}}{t_{0}^{\prime}}+\epsilon_{0}\left(\left(1-\frac{i2D}{m}\right)e^{imt^{\prime}}+\left(1+\frac{i2D}{m}\right)e^{-imt^{\prime}}\right)\right).$
(53)

At this point, it is important to note that for the quantization of
oscillation modes of $\epsilon$, it can be written in terms of creation and
annihilation operators $A$ and $A^{\dagger}$ like

$\epsilon(t)=\epsilon_{0}(Ae^{imt}+A^{\dagger}e^{-imt}).$ (54)

##  3  Coordinate Transformation in Field Space

From a non-static cosmological perspective, once the metric is defined as
$g_{\mu\nu}=a^{2}(t)\eta_{\mu\nu}$, one can rewrite the action in Eq.(6) more
explicitly as

$S=\int
d^{4}x\bigg{[}\frac{1}{2}\bigg{(}\xi^{2}\chi^{2}(\partial_{0}a)^{2}+2\xi^{2}a\chi\partial_{0}a\partial_{0}\chi+\mu^{2}a^{2}(\partial_{0}\chi)^{2}\bigg{)}-\frac{\lambda}{4}a^{4}\chi^{4}\bigg{]}.$
(55)

It is easily seen that this action defines a non-linear $\sigma$ model[21][22]
in which a potential term is added, and can be represented as

$S=\frac{1}{2}\int
d^{4}x\left(G_{bc}(\psi)\partial_{0}\psi^{b}\partial_{0}\psi^{c}-V(\psi)\right)$
(56)

where $\Psi_{b,c}$ corresponds to $a$ and $\chi$. In addition, the metric in
Eq.(56) is given by

$G_{bc}=\begin{pmatrix}\xi^{2}\chi^{2}&\xi^{2}a\chi\\\
\xi^{2}a\chi&\mu^{2}a^{2}\\\ \end{pmatrix}$ (57)

whose scalar curvature can be found zero after straightforward calculations.
Since the metric is flat, the kinetic term of this action can be converted to
that of Klein-Gordon action by a coordinate transformation in field space. In
this way, one can investigate the action in Eq.(55) from the perspective of
the Higgs mechanism. Also, when the following transformation between $G_{bc}$
and $\hat{G}_{bc}$ is achieved, it means we have a non-linear sigma model in
the JBD picture.

$G_{bc}=\begin{pmatrix}\xi^{2}\chi^{2}&\xi^{2}a\chi\\\
\xi^{2}a\chi&\mu^{2}a^{2}\end{pmatrix}\longleftrightarrow\hat{G}_{bc}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$ (58)

Since we are looking for a transformation of the Lagrangian density from the
JBD picture to the Higgs picture, the starting point is to write the line
element of the target space as

$ds^{2}=\frac{1}{2}[\xi^{2}\chi^{2}(da)^{2}+2\xi^{2}a\chi
dad\chi+\mu^{2}a^{2}(d\chi)^{2}].$ (59)

Adding and subtracting the term $\xi^{2}a^{2}(d\chi)^{2}$ in Eq.(59), and then
taking the factor of $\xi^{2}a^{2}\chi^{2}$ outside the parenthesis results in

$ds^{2}=\frac{1}{2}\xi^{2}a^{2}\chi^{2}\left[\left(\frac{d\chi}{\chi}+\frac{da}{a}\right)^{2}+\frac{\mu^{2}-\xi^{2}}{\xi^{2}}\left(\frac{d\chi}{\chi}\right)^{2}\right].$
(60)

Relating $a$ and $\chi$ to new fields $\alpha$ and $\gamma$ as we did before
in Eq.(13) and Eq.(14), gives

$a(\alpha,\gamma)=\alpha e^{-\gamma},$ (61)
$\frac{da}{a}=\frac{d\alpha}{\alpha}-d\gamma,$ (62) $\chi(\gamma)=e^{\gamma},$
(63) $\frac{d\chi}{\chi}=d\gamma,$ (64)

the line element in Eq.(60) turns out to be

$ds^{2}=\frac{1}{2}\xi^{2}\left(d\alpha^{2}+\frac{\mu^{2}-\xi^{2}}{\xi^{2}}\alpha^{2}d\gamma^{2}\right).$
(65)

At this point, another transformation is needed to get rid of the factors and
the following ones are useful to accomplish this.

$\alpha(\rho)=\frac{\rho}{\xi}$ (66) $d\alpha=\frac{d\rho}{\xi}$ (67)
$\gamma(\theta)=\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}\theta$ (68)
$d\gamma=\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}d\theta$ (69)

Substitution of Eq.(67) and Eq.(69) into Eq.(65) yields

$ds^{2}=\frac{1}{2}d\rho^{2}+\frac{1}{2}\rho^{2}d\theta^{2}.$ (70)

Here, $\rho$ and $\theta$ correspond to spherical coordinates. To get
$\hat{G}_{\mu\nu}$ in Eq.(59), it is straightforward to define them as

$\rho(\phi_{3},\phi_{5})=\sqrt{\phi_{3}^{2}+\phi_{5}^{2}},$ (71)
$\theta(\phi_{3},\phi_{5})=\arctan\frac{\phi_{5}}{\phi_{3}}.$ (72)

When these new coordinates are used in Eq.(70), one can write the line element
as desired from the very beginning of this section and it is

$ds^{2}=\frac{1}{2}(d\phi_{3}^{2}+d\phi_{5}^{2}).$ (73)

To write the coordinates $a$ and $\chi$ in terms of $\phi_{3}$ and $\phi_{5}$,
all the transformations can be applied one by one from the beginning to the
end. First of all, after implementing Eq.(66) and Eq.(68) into Eq.(61) and
Eq.(63), $a$ and $\chi$ can be expressed like

$a(\rho,\theta)=\frac{\rho}{\xi}\exp\left(-\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}\theta\right),$
(74) $\chi(\theta)=\exp\left(\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}\theta\right).$
(75)

Then, the transformation from the spherical coordinates to the cartesian ones
results in

$a(\phi_{3},\phi_{5})=\frac{\sqrt{\phi_{3}^{2}+\phi_{5}^{2}}}{\xi}\exp\left(-\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}\arctan\left(\frac{\phi_{5}}{\phi_{3}}\right)\right),$
(76)
$\chi(\phi_{3},\phi_{5})=\exp\left(\frac{\xi}{\sqrt{\mu^{2}-\xi^{2}}}\arctan\left(\frac{\phi_{5}}{\phi_{3}}\right)\right).$
(77)

At this point, it is also possible to state $\phi_{3}$ and $\phi_{5}$ in terms
of $a$ and $\chi$ by carrying out all the transformations back in order. To
start with, because of the spherical ones which have lastly been obtained,
$\phi_{3}$ and $\phi_{5}$ are

$\phi_{3}(\rho,\theta)=\rho\cos\theta,$ (78)
$\phi_{5}(\rho,\theta)=\rho\sin\theta.$ (79)

Thanks to Eq.(66) and Eq.(68), $\rho$ and $\theta$ are found

$\rho(\alpha)=\xi\alpha,$ (80)
$\theta(\gamma)=\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}\gamma,$ (81)

and then using Eq.(80) and Eq.(81) in Eq.(78) and Eq.(79) gives

$\phi_{3}(\alpha,\gamma)=\xi\alpha\cos\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}\gamma\right),$
(82)
$\phi_{5}(\alpha,\gamma)=\xi\alpha\sin\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}\gamma\right).$
(83)

Since, on the basis of Eq.(61) and Eq.(63), $\alpha$ and $\gamma$ are

$\alpha(a,\chi)=a\chi,$ (84) $\gamma(\chi)=\ln\chi,$ (85)

substituting these into Eq.(82) and Eq.(83) gives the scalar fields of the
Higgs picture $\phi_{3}$ and $\phi_{5}$ in terms of those of the JBD picture
$a$ and $\chi$ as

$\phi_{3}(a,\chi)=\xi
a\chi\cos\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}\ln\chi\right),$ (86)
$\phi_{5}(a,\chi)=\xi
a\chi\sin\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}\ln\chi\right).$ (87)

Therefore, in terms of $\phi_{3}$ and $\phi_{5}$, the Lagrangian density in
Eq.(55) can be stated as

$\mathcal{L}=\frac{1}{2}(\partial_{0}\phi_{3})^{2}+\frac{1}{2}(\partial_{0}\phi_{5})^{2}-\frac{\kappa}{4}(\phi^{2}_{3}+\phi^{2}_{5})^{2}$
(88)

where $\kappa=\lambda\xi^{-4}$.

##  4 The Higgs Picture

The Lagrangian density of the Higgs field in doublet form is taken to be

$\mathcal{L}=\partial_{\mu}\Theta^{\dagger}\partial^{\mu}\Theta-V(\Theta)$
(89)

with $\Theta=\frac{1}{\sqrt{2}}\begin{pmatrix}\phi_{1}+i\phi_{2}\\\
\phi_{3}+i\phi_{4}\end{pmatrix}$ where $\phi_{a}$ corresponds to scalar fields
and $a=1,2,3,4$. Furthermore, the potential term can be defined as

$V(\Theta)=-\frac{1}{2}\bar{m}^{2}\Theta^{\dagger}\Theta+\frac{\kappa}{4}(\Theta^{\dagger}\Theta)^{2}$
(90)

where dimensionless constant $\kappa\textgreater 0$ and the scalar fields have
dimension of mass. In addition, the mass term has a minus sign so that for a
time-independent expectation value, spontaneous symmetry breaking occurs. In
terms of the fields $\phi_{a}$, the Lagrangian density can be written as

$\mathcal{L}=\frac{1}{2}\partial_{\mu}\phi_{a}\partial^{\mu}\phi^{a}-\frac{\kappa}{4}(\phi_{a}\phi^{a})^{2}$
(91)

where we put $\bar{m}=0$ so that the potential term in Eq.(91) is purely
quartic.

Note that the symmetry of this Lagrange density is SO(5) which is larger than
the gauge symmetry $SU(2)\times U(1)$ of the standard model. We will extend
this Lagrangian by adding an additional scalar field $\phi_{5}$, so that now

$a=1,2,3,4,5.$

Since the rotational symmetry is spontaneously broken, a fluctuation emerges
about the minimum. Breaking the symmetry annihilates three of four components
of $\Theta$ such that

$\phi_{1}=\phi_{2}=\phi_{4}=0.$ (92)

Moreover, the fields can be independent of spatial coordinates to be
transformable to those of the Jordan-Brans-Dicke theory. Then one obtains the
Lagrangian density in Eq.(88).

At this point, applying field space coordinate transformations in Eq.(86) and
Eq.(87) to the vacuum expectation values and their quantum fluctuations of the
fields of the JBD theory in order to find their correspondence in the Higgs
mechanism gives

$\begin{split}\phi_{3}=\xi\chi_{0}\cos(H(t))\bigg{(}&1+\epsilon_{0}\big{(}Ae^{imt}+A^{\dagger}e^{-imt}\big{)}\\\
&-i\sqrt{\frac{2}{3}}\tan(H(t))\epsilon_{0}\big{(}Ae^{imt}-A^{\dagger}e^{-imt}\big{)}\bigg{)}\end{split}$
(93)

$\begin{split}\phi_{5}=\xi\chi_{0}\sin(H(t))\bigg{(}&1+\epsilon_{0}\big{(}Ae^{imt}+A^{\dagger}e^{-imt}\big{)}\\\
&+i\sqrt{\frac{2}{3}}\cot(H(t))\epsilon_{0}\big{(}Ae^{imt}-A^{\dagger}e^{-imt}\big{)}\bigg{)}\end{split}$
(94)

where

$H(t)=\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}(Dt+E),$ (95)

and

$\chi_{0}=e^{Dt_{0}+E}$ (96)

which is the today’s value of the JBD field.

We note that the system can be quantized by imposing the commutation relation

$\left[A,A^{\dagger}\right]=1.$ (97)

Here, $A$ and $A^{\dagger}$ are the creation and annihilation operators of the
quantum particles and the vucuum expectation values of $\phi_{3}$ and
$\phi_{5}$ are given by

$\langle\phi_{3}\rangle=\xi\chi_{0}\cos\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}Dt\right),$
(98)

$\langle\phi_{5}\rangle=\xi\chi_{0}\sin\left(\frac{\sqrt{\mu^{2}-\xi^{2}}}{\xi}Dt\right).$
(99)

Here, the temporal evolution of the vev of the Higgs field is given by the
argument of cosine in Eq.(98), i.e. the parameter $D$. As it can be checked by
relating the scale factors in two different time scales (conformal and
cosmological time) in Eq.(34) and Eq.(36), $D=-\frac{1}{t^{\prime}_{0}}$ in
which $t^{\prime}$ is the age of the universe in cosmological time. Thus, in
our model $D$ and the evolution of the Higgs field are very slow and the
condition about the particle masses, which has been mentioned before Eq.(2) in
the introduction, is satisfied.

##  5 Conclusion

A cosmological model in which the expansion of the universe is related to the
time dependent vev of the Higgs field has been proposed. Based upon Eq.(1),
the time dependent inertial mass may have another interpretation such that the
time dependence of the Higgs field is part of the metric tensor. With this
approach, the Higgs field has been taken into account as a conformal factor
and related to the scale factor of the FLRW metric. Since it is a more
complete theory of gravitation with respect to Mach’s principle, the JBD
theory has been considered and only the scalar mode of the theory has been
studied. By taking the action of the scale factor $a(t)$ and the JBD field
$\chi(t)$ as depending only on time, the relation between the JBD cosmology
and the Higgs mechanism has been established with the field space coordinate
transformations (Eq.(76), Eq.(77), Eq.(86) and Eq.(87)) for negative values of
the JBD parameter. Although solar system experiments predict the original JBD
parameter $\omega$ to be a big positive number[23][24], scenarios based on its
negative values[25, 26, 27, 28, 29, 30] are viable and quite common in the
literature for cosmological scales. In addition to this, negative values of
the coupling parameter are encountered in the applications of the low-energy
effective action of the string theory[31][32] such that the dilatonic coupling
constant is chosen as $\omega=-1$ for the string frame[33, 34, 35]. Finally,
oscillation modes about the vacuum in both pictures have been found and it has
been shown that they are quantizable.

## References

  * [1] G. Aad, T. Abajyan, B. Abbott, J. Abdallah, S. A. Khalek, A. A. Abdelalim, R. Aben, B. Abi, M. Abolins, O. AbouZeid, et al., “Observation of a new particle in the search for the standard model higgs boson with the atlas detector at the lhc,” Physics Letters B, vol. 716, no. 1, pp. 1–29, 2012\.
  * [2] P. W. Higgs, “Broken symmetries and the masses of gauge bosons,” Physical Review Letters, vol. 13, no. 16, p. 508, 1964.
  * [3] S. Weinberg, “Conceptual foundations of the unified theory of weak and electromagnetic interaction,” in Origin Of Symmetries, pp. 215–223, World Scientific, 1991.
  * [4] A. Salam, “Gauge unification of fundamental forces,” Reviews of Modern Physics, vol. 52, no. 3, p. 525, 1980.
  * [5] S. L. Glashow, “Towards a unified theory: Threads in a tapestry,” Reviews of Modern Physics, vol. 52, no. 3, p. 539, 1980.
  * [6] R. v. Eotvos, “Beitrage zum gesetze der proportionalitat von tragheit und gravitat,” Ann. Phys., vol. 68, pp. 11–66, 1922.
  * [7] D. W. Sciama, “On the origin of inertia,” Monthly Notices of the Royal Astronomical Society, vol. 113, no. 1, pp. 34–42, 1953.
  * [8] M. Arik and T. Tok, “The scalar mode of gravity,” arXiv preprint arXiv:2001.02347, 2020.
  * [9] A. Friedman, “Über die krümmung des raumes,” Zeitschrift für Physik, vol. 10, no. 1, pp. 377–386, 1922.
  * [10] G. Lemaître, “Expansion of the universe, the expanding universe,” Monthly Notices of the Royal Astronomical Society, vol. 91, pp. 490–501, 1931\.
  * [11] H. P. Robertson, “Kinematics and world-structure,” The Astrophysical Journal, vol. 82, p. 284, 1935.
  * [12] A. G. Walker, “On milne’s theory of world-structure,” Proceedings of the London Mathematical Society, vol. 2, no. 1, pp. 90–127, 1937.
  * [13] P. J. E. Peebles and B. Ratra, “The cosmological constant and dark energy,” Reviews of modern physics, vol. 75, no. 2, p. 559, 2003.
  * [14] V. Sahni, “Dark matter and dark energy,” in The Physics of the Early Universe, pp. 141–179, Springer, 2004.
  * [15] C. Brans and R. H. Dicke, “Mach’s principle and a relativistic theory of gravitation,” Physical review, vol. 124, no. 3, p. 925, 1961.
  * [16] D. J. Raine, “Mach’s principle in general relativity,” Monthly Notices of the Royal Astronomical Society, vol. 171, no. 3, pp. 507–528, 1975.
  * [17] A. Joyce, L. Lombriser, and F. Schmidt, “Dark energy versus modified gravity,” Annual Review of Nuclear and Particle Science, vol. 66, pp. 95–122, 2016.
  * [18] P. Jordan, “Zum gegenwärtigen stand der diracschen kosmologischen hypothesen,” Zeitschrift für Physik, vol. 157, no. 1, pp. 112–121, 1959.
  * [19] R. H. Dicke, “New research on old gravitation,” Science, vol. 129, no. 3349, pp. 621–624, 1959.
  * [20] R. H. Dicke, “Gravitation—an enigma,” American Scientist, vol. 47, no. 1, pp. 25–40, 1959.
  * [21] M. Gell-Mann and M. Lévy, “The axial vector current in beta decay,” Il Nuovo Cimento (1955-1965), vol. 16, no. 4, pp. 705–726, 1960.
  * [22] M. E. Peskin and D. V. Schroeder, “An introduction to quantum field theory (boulder, co),” 1995.
  * [23] Y.-C. Li, F.-Q. Wu, and X. Chen, “Constraints on the brans-dicke gravity theory with the planck data,” Physical Review D, vol. 88, no. 8, p. 084053, 2013.
  * [24] C. M. Will, Theory and experiment in gravitational physics.  Cambridge university press, 2018.
  * [25] O. Bertolami and P. Martins, “Nonminimal coupling and quintessence,” Physical Review D, vol. 61, no. 6, p. 064007, 2000.
  * [26] S. Sen and A. Sen, “Late time acceleration in brans-dicke cosmology,” Physical Review D, vol. 63, no. 12, p. 124006, 2001.
  * [27] S. Sen and T. Seshadri, “Self interacting brans–dicke cosmology and quintessence,” International Journal of Modern Physics D, vol. 12, no. 03, pp. 445–460, 2003.
  * [28] N. Banerjee and D. Pavon, “A quintessence scalar field in brans-dicke theory,” Classical and Quantum Gravity, vol. 18, no. 4, p. 593, 2001.
  * [29] A. Batista, J. Fabris, and R. de Sa Ribeiro, “A remark on brans–dicke cosmological dust solutions with negative $\omega$,” General Relativity and Gravitation, vol. 33, no. 7, pp. 1237–1244, 2001.
  * [30] J. Fabris, S. Gonçalves, and R. Ribeiro, “Late time accelerated brans-dicke pressureless solutions and the supernovae type ia data,” arXiv preprint astro-ph/0510779, 2005.
  * [31] J. Fabris, R. Furtado, P. Peter, and N. Pinto-Neto, “Regular cosmological bouncing solutions in low energy effective action from string theories,” Physical Review D, vol. 67, no. 12, p. 124003, 2003.
  * [32] G. Calcagni, S. Tsujikawa, and M. Sami, “Dark energy and cosmological solutions in second-order string gravity,” Classical and Quantum Gravity, vol. 22, no. 19, p. 3977, 2005.
  * [33] E. J. Copeland, A. Lahiri, and D. Wands, “Low energy effective string cosmology,” Physical Review D, vol. 50, no. 8, p. 4868, 1994.
  * [34] M. Gasperini, J. Maharana, and G. Veneziano, “Graceful exit in quantum string cosmology,” Nuclear Physics B, vol. 472, no. 1-2, pp. 349–360, 1996.
  * [35] D. Wands, “String-inspired cosmology,” Classical and Quantum Gravity, vol. 19, no. 13, p. 3403, 2002.


# Counting cycles in planar triangulations

On-Hei Solomon LO111Département d’informatique et de recherche opérationnelle,
Université de Montréal, Pavillon André-Aisenstadt, 2920, chemin de la Tour,
Montréal, Québec H3T 1J4, Canada. E-mail address<EMAIL_ADDRESS>and
Carol T. ZAMFIRESCU222Department of Applied Mathematics, Computer Science and
Statistics, Ghent University, Krijgslaan 281 - S9, 9000 Ghent, Belgium and
Department of Mathematics, Babeş-Bolyai University, Cluj-Napoca, Roumania.
E-mail address<EMAIL_ADDRESS>
Abstract. We investigate the minimum number of cycles of specified lengths in
planar $n$-vertex triangulations $G$. It is proven that this number is
$\Omega(n)$ for any cycle length at most $3+\max\\{{\rm
rad}(G^{*}),\lceil(\frac{n-3}{2})^{\log_{3}2}\rceil\\}$, where ${\rm
rad}(G^{*})$ denotes the radius of the triangulation’s dual, which is at least
logarithmic but can be linear in the order of the triangulation. We also show
that there exist planar hamiltonian $n$-vertex triangulations containing
$O(n)$ many $k$-cycles for any $k\in\\{\lceil
n-\sqrt[5]{n}\rceil,\ldots,n\\}$. Furthermore, we prove that planar
4-connected $n$-vertex triangulations contain $\Omega(n)$ many $k$-cycles for
every $k\in\\{3,\ldots,n\\}$, and that, under certain additional conditions,
they contain $\Omega(n^{2})$ $k$-cycles for many values of $k$, including $n$.

Key words. Planar triangulation, cycle enumeration.

MSC 2020. 05C10, 05C30, 05C38, 05C45.

##  1 Introduction

In this paper, a _triangulation_ shall be a plane graph unless explicitly
stated otherwise, i.e. an embedded planar graph, in which every face is a
triangle, but we exclude $K_{3}$ so that a triangulation shall here always be
3-connected. In a graph $G$, the length of a shortest cycle in $G$ is called
its _girth_ , and the length of a longest cycle its _circumference_. The
latter will be abbreviated to ${\rm circ}(G)$. For a graph $G$, its _cycle
spectrum_ is the set of all lengths of cycles occurring in $G$. We will here
be interested in counting cycles in triangulations. For a graph $G$, a set
$X\subset V(G)$ is a _cut_ if $G-X$ has more connected components than $G$. A
cut on $k$ vertices is a _$k$ -cut_.

Hitherto, most results on the enumeration of cycles in $n$-vertex
triangulations $G$ focus on the two ends of the cycle spectrum. Historically,
the first result which can be interpreted as a statement on counting cycles in
triangulations is Euler’s formula, which implies that $G$ contains $\Omega(n)$
many 3-cycles. Hakimi and Schmeichel [9] presented tight upper and lower
bounds on the number of 3-cycles and 4-cycles as well as those graphs for
which the bounds are attained except for a few cases which were later
completed by Alameddine [2]. In particular, it follows from [9] that any
$n$-vertex triangulation $G$ contains $\Theta(n)$ many 3-cycles as well as
$\Omega(n)$ and $O(n^{2})$ many 4-cycles. There exist infinitely many
triangulations with a linear number of 3-cycles (4-cycles), for instance
4-connected (5-connected) triangulations: a 3-cycle (4-cycle) in such a graph
cannot be separating, so it must be the boundary of a triangular face (the
symmetric difference of the boundaries of two triangular faces sharing an
edge).

Hakimi and Schmeichel also showed that there must occur $\Omega(n)$ and
$O(n^{2})$ many 5-cycles. They conjectured a precise upper bound of
$2n^{2}-10n+12$ and this was confirmed only very recently [8]. Moreover, they
proved that in an $n$-vertex triangulation there are at least $6n$ 5-cycles,
and there are infinitely many triangulations attaining this bound. Since in
triangulations every inclusion-minimal cut induces a cycle, these results
immediately give information on the number of 3-, 4-, and 5-cuts in
triangulations. For $k>5$, Hakimi and Schmeichel write that they “ _have no
interesting lower bound_ ” for the number of $k$-cycles. This motivates the
following question.

######  Problem 1.

What can be said, asymptotically, about the minimum number of $k$-cycles
occurring in a given triangulation for $k>5$?

Hakimi and Schmeichel [9] also proved that every triangulation is _weakly
pancyclic_ , i.e. it contains cycles of all lengths between its girth, which
is always three, and circumference. It is however _not_ true that every
$n$-vertex triangulation $G$ contains $\Omega(n)$ many $k$-cycles for every
integer $k$ with $3\leq k\leq{\rm circ}(G)$: Hakimi, Schmeichel, and Thomassen
[10] constructed an infinite family of triangulations with exactly four
hamiltonian cycles. And one cannot do better: Kratochvil and Zeps [12] proved
that if a triangulation different from $K_{4}$ contains a hamiltonian cycle,
then it contains at least four of them. They also show that this theorem holds
for triangulations of arbitrary surfaces.

On the one hand, the results we just mentioned illustrate that a hamiltonian
triangulation may have very few hamiltonian cycles; on the other hand, a
triangulation may be far from hamiltonian. In the sixties Moon and Moser [19]
proved that there are infinitely many $n$-vertex triangulations that have
circumference at most $9n^{\log_{3}2}$, and 40 years later Chen and Yu [6]
showed that this upper bound is best possible up to the constant factor.

In 1979 Hakimi, Schmeichel, and Thomassen proved that every 4-connected
$n$-vertex triangulation contains at least $n/\log_{2}n$ hamiltonian cycles.
This was improved in 2018 when Brinkmann, Souffriau, and Van Cleemput [3]
showed that there is a linear number of hamiltonian cycles in 4-connected
triangulations. For very recent developments concerning the enumeration of
hamiltonian cycles in triangulations, we refer the reader to [1, 15, 13, 17].
It follows from a classic paper of Tutte [25] that in 4-connected $n$-vertex
triangulations the number of $(n-1)$-cycles is also at least linear in $n$,
and one can infer from papers of Thomas and Yu [24] and Sanders [22] that the
same holds for $(n-2)$\- and $(n-3)$-cycles. (In fact, [24] even yields a
quadratic number of $(n-2)$-cycles; we shall come back to this deep result
later on.) This naturally leads to the following question.

######  Problem 2.

Are $4$-connected $n$-vertex triangulations linearly pancyclic, i.e. do they
contain $\Omega(n)$ many $k$-cycles for every $k\in\\{3,\ldots,n\\}$?

Mohar and Shantanam [18] have recently proven that in a 4-connected
triangulation on $n$ vertices, every edge is contained in cycles of $n-2$
pairwise distinct lengths. They also showed that there exists
$\frac{5}{12}\leq\lambda\leq\frac{2}{3}$ such that any edge in any planar
4-connected $n$-vertex graph is contained in cycles of $\lambda(n-2)$ pairwise
distinct lengths, and conjectured that $\lambda=\frac{2}{3}$. The lower bound
$\frac{5}{12}(n-2)$ was improved to $\frac{n}{2}+1$ in [16].

We mention that many problems in extremal graph theory revolve around finding,
for a fixed graph $H$, the _maximum_ number of subgraphs isomorphic to $H$ in
an $n$-vertex graph in some class ${\cal G}$. For graphs $H$ and $G$ and a
surface $\Sigma$, let $C(H,\Sigma,n)$ be the maximum number of copies of $H$
in $G$, where the maximum is taken over all $n$-vertex graphs $G$ that embed
in $\Sigma$. A very recent manuscript of Huynh, Joret, and Wood [11] gives a
panoramic view of results in this area and determines, for any fixed surface
$\Sigma$ and any fixed graph $H$, the asymptotic behaviour of $C(H,\Sigma,n)$
as $n\to\infty$.

Let $G$ be an embedded graph. We denote by $G^{*}$ the dual of $G$. If $G$ is
a plane graph, the _weak dual_ of $G$ is obtained from $G^{*}$ by deleting the
vertex corresponding to the unbounded face of $G$. For a vertex $v$ in $G$ let
$v^{*}$ be the face of $G^{*}$ corresponding to the vertex $v$. For distinct
vertices $v$ and $w$ in a graph $G$, we call a path with end-vertex $v$ a _$v$
-path_, and a $v$-path with end-vertex $w$ a _$vw$ -path_. For a path $P$, its
_length_ is $|E(P)|$. The _distance_ $d_{G}(v,w)$ between $v$ and $w$ is
defined as the length of a shortest $vw$-path in $G$. Whenever $G$ is clear
from context, we replace $d_{G}$ by $d$. For a graph $G$, its _radius_ and
_diameter_ are defined as

${\rm rad}(G):=\min_{v\in V(G)}\max_{w\in V(G)}d(v,w)\qquad{\rm and}\qquad{\rm
diam}(G):=\max_{v\in V(G)}\max_{w\in V(G)}d(v,w),$

respectively. In this paper, a face will always include the facial walk
bounding it. For a plane graph $G$, we denote by $F(G)$ its set of faces. For
a cycle $C$ in $G$, let ${\rm int}C$ be the set of all vertices inside of $C$
but not on $C$, and put ${\rm Int}C:=V(C)\cup{\rm int}C$. The former will be
called the _interior_ of $C$, the latter the _closed interior_ of $C$. The
_exterior_ ${\rm ext}C$ and _closed exterior_ ${\rm Ext}C$ are defined
analogously. For any $v\in V(G)$, the _neighbourhood_ $N_{G}(v)$ of $v$ in $G$
is defined to be the set of vertices adjacent to $v$ in $G$. We simply write
$N(v)$ if it causes no ambiguity.

In Section 2 we show that the minimum number of $k$-cycles occurring in an
$n$-vertex triangulation $G$ is $\Omega(n)$ for any
$k\in\\{3,\ldots,3+\max\\{{\rm
rad}(G^{*}),\lceil(\frac{n-3}{2})^{\log_{3}2}\rceil\\}\\}$. In Section 3,
motivated by finding hamiltonian triangulations—a superset of 4-connected
triangulations—with few long cycles, it is shown that there exist hamiltonian
$n$-vertex triangulations containing $O(n)$ many $k$-cycles for any
$k\in\\{\lceil n-\sqrt[5]{n}\rceil,\ldots,n\\}$. Moreover, we prove that
4-connected $n$-vertex triangulations contain $\Omega(n)$ many $k$-cycles for
any $k\in\\{3,\ldots,n\\}$, and that, under certain additional conditions,
they contain $\Omega(n^{2})$ $k$-cycles for many values of $k$, including $n$.
The article concludes with comments on directions of future research and open
problems in Section 4.

##  2 Linearly many short cycles

We here show that an $n$-vertex triangulation contains linearly many cycles of
every length that is at most the radius of the triangulation’s dual or
$O(n^{\log_{3}2})$, whichever is greater.

The following definition will be useful. Let $G$ be a 2-connected plane graph.
For a connected subgraph $H$ of $G^{*}$, put

$H^{*}=\bigcup\\{v^{*}:v\in V(H)\\},$

i.e. a union of faces. Furthermore, let $\partial H^{*}$ be the subgraph of
$H^{*}$ defined as

$(V(H^{*}),\\{vw\in E(H^{*}):vw\text{\;is incident with exactly one face
from\;}H^{*}\\})$

from which all isolated vertices are removed.

We will make use of the following lemma. A _near triangulation_ is a
2-connected plane graph all of whose bounded faces are triangular.

######  Lemma 1.

Let $G$ be a near triangulation on at least four vertices and $D$ be the weak
dual of $G$. If at most two bounded triangular faces in $G$ contain two edges
of $\partial D^{*}$ and any bounded triangular face in $G$ that has some edge
of $\partial D^{*}$ has all three of its vertices contained in $\partial
D^{*}$, then $D$ is a path.

###### Proof.

We prove the statement by induction on the number of vertices of $G$. If
$|V(G)|=4$, then $G$ has exactly two bounded faces and $D$ is a path of length
one.

If $|V(G)|>4$, then there must be a triangular face $\Delta$ on vertices
$v_{1},v_{2},v_{3}$ such that $\Delta$ has only one edge $v_{1}v_{2}$
contained in $\partial D^{*}$ and $v_{3}$ is in $\partial D^{*}$ as well. Note
that $D-\Delta^{*}$ has precisely two components $H_{1},H_{2}$. Denote by
$G_{1}$ and $G_{2}$ the near triangulations induced by $D-H_{1}$ and
$D-H_{2}$, respectively. We may assume that $G_{1}$ has at most two bounded
triangular faces each containing two edges of $\partial D_{1}^{*}$, where
$D_{1}$ is the weak dual of $G_{1}$. By the induction hypothesis, $D_{1}$ is a
path. Moreover, this implies that $G_{2}$ has at most two bounded triangular
faces each containing two edges of $\partial D_{2}^{*}$ as $D_{1}$ has an end-
vertex other than $\Delta^{*}$, where $D_{2}$ denotes the weak dual of
$G_{2}$. Again, by the induction hypothesis, $D_{2}$ and hence $D$ are paths.
∎

For our first theorem’s proof we also need the following technical framework.
Brinkmann, Souffriau, and Van Cleemput [3] introduced so-called counting bases
in order to enumerate hamiltonian cycles in planar graphs. Making use of their
method, we are able to solve Problem 2 affirmatively; the details will be
given in the next section. We recall the main ingredients of this technique
which we will then slightly modify so that we can count cycles of a specified
length.

Let $G$ be a graph. A _counting base_ for $G$ is defined to be a triple
$(\mathcal{P},\\{\mathcal{C}_{P}\\}_{P\in\mathcal{P}},\sigma)$, where
$\mathcal{P}\subseteq 2^{E(G)}$, $\mathcal{C}_{P}$ is a family of cycles in
$G$ for each $P\in\mathcal{P}$, and $\sigma:\mathcal{P}\rightarrow\mathcal{P}$
is a function satisfying the following properties.

  1. (i)

For every $P\in\mathcal{P}$, $\mathcal{C}_{P}$ is non-empty, and for every
$C\in\mathcal{C}_{P}$, $P\subseteq E(C)$;

  2. (ii)

for every $P\in\mathcal{P}$, $\sigma(\sigma(P))=P\not\subseteq\sigma(P)$ and
for every $C\in\mathcal{C}_{P}$,
$\sigma(C,P):=(C-P)\cup\sigma(P)\in\mathcal{C}_{\sigma(P)}$ (here we extend
the function $\sigma$ with abuse of notation) and
$\sigma(\sigma(C,P),\sigma(P))=C$;

  3. (iii)

for any distinct $P_{1},P_{2}\in\mathcal{P}$ and any
$C\in\mathcal{C}_{P_{1}}\cap\mathcal{C}_{P_{2}}$,
$\sigma(C,P_{1})\neq\sigma(C,P_{2})$;

  4. (iv)

for any $P_{1},P_{2}\in\mathcal{P}$ with $P_{1}\cap P_{2}=\emptyset$ and any
$C\in\mathcal{C}_{P_{1}}\cap\mathcal{C}_{P_{2}}$,
$\sigma(C,P_{1})\in\mathcal{C}_{P_{2}}$.

Condition (ii) immediately implies that for every $P\in\mathcal{P}$, $P$ is
non-empty and for every $C\in\mathcal{C}_{P}$, $P\not\subseteq E(\sigma(C,P))$
and hence $\sigma(C,P)\notin\mathcal{C}_{P}$.

We will give a lower bound on the number of cycles in
$\bigcup_{P\in\mathcal{P}}\mathcal{C}_{P}$ by relating
$|\bigcup_{P\in\mathcal{P}}\mathcal{C}_{P}|$ to $|\mathcal{P}|$. To this end,
we need to factor out the “overlap” when counting the number of cycles by
considering the following notion. Given a counting base
$\mathfrak{C}=(\mathcal{P},\\{\mathcal{C}_{P}\\}_{P\in\mathcal{P}},\sigma)$,
we define for $P\in\mathcal{P}$ and $C\in\mathcal{C}_{P}$ the _overlap_

$\mathbf{o}_{\mathfrak{C}}(C,P):=|\\{P^{\prime}\in\mathcal{P}:P\cap
P^{\prime}\neq\emptyset\textrm{ and }C\in\mathcal{C}_{P^{\prime}}\\}|.$

Furthermore, put

$\mathbf{O}_{\mathfrak{C}}:=\max_{P\in\mathcal{P},\,C\in\mathcal{C}_{P}}\mathbf{o}_{\mathfrak{C}}(C,P).$

Note that $\mathbf{o}_{\mathfrak{C}}(C,P)\geq 1$ for any $P\in\mathcal{P}$ and
any $C\in\mathcal{C}_{P}$; in particular, $\mathbf{O}_{\mathfrak{C}}\geq 1$.

The following powerful tool is due to Brinkmann, Souffriau, and Van Cleemput
[3]. We include a proof for completeness’ sake.

Counting Base Lemma ([3, Theorem 1]). _Let $G$ be a graph and
$\mathfrak{C}=(\mathcal{P},\\{\mathcal{C}_{P}\\}_{P\in\mathcal{P}},\sigma)\neq\emptyset$
a counting base for $G$. Then_

$\left|\bigcup_{P\in\mathcal{P}}\mathcal{C}_{P}\right|\geq\frac{|\mathcal{P}|}{\mathbf{O}_{\mathfrak{C}}}.$

###### Proof.

For a cycle $C$ in $G$, let
$m(C):=|\\{P\in\mathcal{P}:C\in\mathcal{C}_{P}\\}|$. We have

$\left|\bigcup_{p\in\mathcal{P}}\mathcal{C}_{P}\right|=\sum_{P\in\mathcal{P}}\sum_{C\in\mathcal{C}_{P}}\frac{1}{m(C)}.$

It is left to show that

$\sum_{C\in\mathcal{C}_{P}}\frac{1}{m(C)}\geq\frac{1}{\mathbf{O}_{\mathfrak{C}}}$

for every $P\in\mathcal{P}$, an inequality we abbreviate by $(\dagger)$.

Let $P$ be any element of $\mathcal{P}$, and let $C^{0}\in\mathcal{C}_{P}$. We
may assume that $m(C^{0})>\mathbf{O}_{\mathfrak{C}}$. Then there exist $t\geq
m(C^{0})-\mathbf{O}_{\mathfrak{C}}$ and $P^{1},\dots,P^{t}\in\mathcal{P}$ such
that $C^{0}\in\mathcal{C}_{P^{i}}$ and $P^{i}\cap P=\emptyset$ for every
$i\in\\{1,\dots,t\\}$. Note that
$C^{0},\sigma(C^{0},P^{1}),\dots,\sigma(C^{0},P^{t})$ are $t+1$ pairwise
distinct cycles in $\mathcal{C}_{P}$.

We claim that $m(\sigma(C^{0},P^{i}))\leq
m(C^{0})-1+\mathbf{O}_{\mathfrak{C}}$. By definition,

$m(\sigma(C^{0},P^{i}))=|\\{P^{\prime}\in\mathcal{P}:\sigma(C^{0},P^{i})\in\mathcal{C}_{P^{\prime}}\\}|.$

We distinguish between two cases, depending on whether or not
$C^{0}\in\mathcal{C}_{P^{\prime}}$ holds. As
$\sigma(C^{0},P^{i})\notin\mathcal{C}_{P^{i}}$, there are at most $m(C^{0})-1$
many $P^{\prime}$ satisfying $\sigma(C^{0},P^{i})\in\mathcal{C}_{P^{\prime}}$
and $C^{0}\in\mathcal{C}_{P^{\prime}}$. For $P^{\prime}$ satisfying
$\sigma(C^{0},P^{i})\in\mathcal{C}_{P^{\prime}}$ and
$C^{0}\notin\mathcal{C}_{P^{\prime}}$, by the definition of a counting base,
we have that $P^{\prime}\cap\sigma(P^{i})\neq\emptyset$. Therefore, there are
at most $\mathbf{o}_{\mathfrak{C}}(\sigma(C^{0},P^{i}),\sigma(P^{i}))$ many
such $P^{\prime}$. This justifies the claim.

As $\mathbf{O}_{\mathfrak{C}}\geq 1$, we have

$\sum_{C\in\mathcal{C}_{P}}\frac{1}{m(C)}\geq\frac{1}{m(C^{0})}+\sum_{i=1}^{t}\frac{1}{\sigma(C^{0},P^{i})}\geq\frac{1}{m(C^{0})}+\frac{m(C^{0})-\mathbf{O}_{\mathfrak{C}}}{m(C^{0})-1+\mathbf{O}_{\mathfrak{C}}}\geq\frac{m(C^{0})-\mathbf{O}_{\mathfrak{C}}+1}{m(C^{0})+\mathbf{O}_{\mathfrak{C}}-1}.$

Since
$\frac{m(C^{0})-\mathbf{O}_{\mathfrak{C}}+1}{m(C^{0})+\mathbf{O}_{\mathfrak{C}}-1}$
is non-decreasing in $m(C^{0})$ and $m(C^{0})\geq\mathbf{O}_{\mathfrak{C}}+1$,
$(\dagger)$ holds. ∎

We also require the following lemma (more precisely, its second part—its first
part will be useful later on). Thereafter, we can state and prove our first
main result.

######  Lemma 2.

Let $G$ be a near triangulation, $C$ be the boundary cycle of the unbounded
face of $G$, and $v_{1}v_{2},v_{2}v_{3},v_{3}v_{4}$ be three consecutive edges
in $C$. Then the following hold.

  1. (i)

There exists a $k$-cycle in $G$ containing $v_{1}v_{2}v_{3}$ for every $k\in
I:=\\{\min\\{|E(C)|,|N(v_{2})|+1\\},\ldots,\max\\{|E(C)|,|N(v_{2})|+1\\}\\}$.

  2. (ii)

If $v_{1}\neq v_{4}$ and $v_{2}v_{3}v_{4}v_{2}$ is a triangular facial
boundary, then there exists a $k$-cycle in $G$ containing
$v_{1}v_{2}v_{3}v_{4}$ for every $k\in I$.

###### Proof.

Let $D_{0}$ be the weak dual of $G$. We construct a sequence of
$\ell:=|V(D_{0})|-|N(v_{2})|+1$ subgraphs $D_{1},\dots,D_{\ell}$ of $D_{0}$ by
removing vertices one-by-one from $D_{0}$ as follows. Suppose we have already
constructed $D_{i}$ for some $i$ with $0\leq i<\ell$. We may take $v\in
V(D_{i})$ such that $D_{i}-v$ remains connected and the triangular face
$v^{*}$ does not contain $v_{2}$ but some edge in $\partial D_{i}^{*}$. Define
$D_{i+1}:=D_{i}-v$. It is not hard to see that this iterative procedure holds,
every $\partial D_{i}^{*}$ is a cycle containing $v_{1}v_{2}v_{3}$, $\partial
D_{\ell}^{*}$ is the cycle on $\\{v_{2}\\}\cup N(v_{2})$, and

$\big{|}|E(\partial D_{i}^{*})|-|E(\partial D_{i+1}^{*})|\big{|}=1$

for all $i\in\\{0,\ldots,\ell-1\\}$. Therefore, among these $\ell+1$ cycles
$\partial D_{i}^{*}$, there are $k$-cycles containing $v_{1}v_{2}v_{3}$ for
all $k\in I$. This proves the first statement. Moreover, if $v_{1}\neq v_{4}$
and $\\{v_{2},v_{3},v_{4}\\}$ induces a triangular face, then every cycle
containing $v_{1}v_{2}v_{3}$ must contain $v_{3}v_{4}$ as well. This thus
proves the second statement. ∎

######  Theorem 1.

Let $G$ be an $n$-vertex triangulation. For every integer $k$ with $3\leq
k\leq 3+\max\\{{\rm rad}(G^{*}),\lceil(\frac{n-3}{2})^{\log_{3}2}\rceil\\}$
there are $\Omega(n)$ many $k$-cycles in $G$.

###### Proof.

We first show that for every integer $k$ with $3\leq k\leq 3+{\rm rad}(G^{*})$
there are $\Omega(n)$ many $k$-cycles in $G$. Let $v$ and $w$ be two vertices
in $G^{*}$. We claim that there is a $vw$-path $P$ in $G^{*}$ such that $P$ is
an induced path in $G^{*}$ and $\partial P^{*}$ is a cycle containing two
edges of $v^{*}$ and two edges of $w^{*}$. Assume that the unbounded face of
$G$ is neither $v^{*}$ nor $w^{*}$, and denote by $D_{0}$ the weak dual of
$G$. We construct a sequence of subgraphs $D_{1},D_{2},\ldots$ of $D_{0}$ by
successively removing, one-by-one, vertices from $D_{0}$ as follows. If there
is a vertex $u$ in $D_{i}$ that is neither $v$ nor $w$ such that either
$\partial D_{i}^{*}$ contains two edges of $u^{*}$, or $\partial D_{i}^{*}$
contains one edge of $u^{*}$ but not all vertices of $u^{*}$, then we obtain
$D_{i+1}$ by deleting $u$ from $D_{i}$. It is clear that $D_{i}$ is always a
connected induced subgraph of $D_{0}$ containing $v,w$ and $\partial
D_{i}^{*}$ is a cycle for all $i$.

Let $D_{\ell}$ be the graph we obtain when no further vertex can be removed.
Then there is no vertex $v_{0}\in V(G)$ lying in the interior of $\partial
D_{\ell}^{*}$, as otherwise there would exist pairwise distinct vertices
$v_{1},v_{2},v_{3}$ in $\partial D_{\ell}^{*}$ which can be reached from
$v_{0}$ by a $v_{0}v_{1}$-path, a $v_{0}v_{2}$-path, and a $v_{0}v_{3}$-path,
all three of which are pairwise internally disjoint. It is clear that in each
of the three regions of the closed interior of $\partial D_{\ell}^{*}$ formed
by these three paths, there is a bounded triangular face which either has two
edges of $\partial D_{\ell}^{*}$ or has an edge of $\partial D_{\ell}^{*}$ and
a vertex not in $\partial D_{\ell}^{*}$, yielding a contradiction, as we
should then remove the corresponding vertex of one such face that is neither
$v$ nor $w$ from $D_{\ell}$. Therefore, we can apply Lemma 1 to deduce that
$D_{\ell}$ is a path. It is also obvious that $v$ and $w$ are the end-vertices
of $D_{\ell}$. This implies that $\partial D_{\ell}^{*}$ is a cycle containing
two edges of $v^{*}$ and two edges of $w^{*}$.

Let $v$ be any vertex in $G^{*}$. By the claim above, we can find a $v$-path
$P$ in $G^{*}$ of length $r:={\rm rad}(G^{*})$ such that $P$ is an induced
path and $\partial P^{*}$ is a cycle. We denote the vertices of $P$ by
$v,w_{1},\ldots,w_{r}$. Let $P_{i}\subseteq P$ be the $vw_{i}$-path for all
$i\in\\{1,\ldots,r\\}$. As $\partial P^{*}$ is a cycle, each $\partial
P_{i}^{*}$ is a cycle. The set ${\cal C}:=\\{\partial P_{i}^{*}\\}_{i=1}^{r}$
contains exactly one $k$-cycle for each $k\in\\{4,\ldots,r+3\\}$, and there
exist edges $e$ and $f$ in $v^{*}$ such that the edge-set of the intersection
of any cycle in ${\cal C}$ with $v^{*}$ is $\\{e,f\\}$. We call this property
$(\dagger)$.

We repeat the above procedure for every vertex in $G^{*}$, of which there are
$2n-4$ by Euler’s formula. In this fashion, due to $(\dagger)$, any given
cycle was counted at most twice. Hence, there exist at least $n-2$ $k$-cycles
for every $k$ with $3\leq k\leq r+3$. We remark that the cycles found in the
aforementioned proof have an empty interior or exterior. We have completed the
first part of the proof.

We now prove that for every integer $k$ with $3\leq k\leq
3+\lceil(\frac{n-3}{2})^{\log_{3}2}\rceil$ there are $\Omega(n)$ many
$k$-cycles in $G$. For $k\in\\{3,4,5\\}$ a linear lower bound on the number of
$k$-cycles follows from Euler’s formula and results of Hakimi and Schmeichel
[9], as mentioned in the Introduction. The case $k=6$ can be inferred from the
first part of this proof. So we may assume $7\leq
k\leq\lceil(\frac{n-3}{2})^{\log_{3}2}\rceil+3$. An edge $uv\in E(G)$ is said
to be _good_ if $u$ and $v$ have precisely two common neighbours $w_{1}$ and
$w_{2}$, and $u$ or $v$ has degree at most 6. We also call $w_{1}uvw_{2}$ and
$w_{1}vuw_{2}$ _zigzag-paths_ with the _internal edge_ $uv$, and we identify a
zigzag-path with its edge set. We define $\mathcal{P}$ to be the set of
zigzag-paths having a good internal edge.

Let $v\in V(G)$. Observe that $N_{G}(v)$ induces an outerplanar subgraph
$H_{v}$ of $G$, and hence $H_{v}$ has at least two vertices $v_{1},v_{2}$ of
degree 2. It is not hard to see that $vv_{1}$ and $vv_{2}$ are good edges
provided that $v$ has degree at most 6 in $G$. Together with the fact that $G$
has average degree less than 6, we conclude that $|\mathcal{P}|\in\Omega(n)$.

For any $P\in\mathcal{P}$, we define $\mathcal{C}^{k}_{P}$ to be the family of
$k$-cycles $C$ with $E(C)\supset P$ and $\sigma(P):=w_{1}vuw_{2}$ when
$P=w_{1}uvw_{2}$. We claim that
$\mathfrak{C}_{k}=(\mathcal{P},\\{\mathcal{C}^{k}_{P}\\}_{P\in\mathcal{P}},\sigma)$
is a counting base. It suffices to show that
$\mathcal{C}^{k}_{P}\neq\emptyset$ for every $P\in\mathcal{P}$. Let
$P=w_{1}uvw_{2}$ be an element of $\mathcal{P}$. We may assume that $v$ has
degree at most 6.

Recall that a _circuit graph_ is a pair $(G_{0},C_{0})$, where $G_{0}$ is a
2-connected plane graph and $C_{0}$ is a facial cycle of $G_{0}$, such that
for any 2-cut $S$ of $G_{0}$, every component of $G_{0}-S$ contains a vertex
of $C$.

Now, we take $G_{0}:=G-u-v$. Since $uv$ is a good edge, $u,v$ lie in a face
which is bounded by a cycle, denoted by $C_{0}$, containing $w_{1},w_{2}$.
Therefore $(G_{0},C_{0})$ is a circuit graph. By [23, Lemma 2.3] there is a
$w_{1}w_{2}$-path in $G_{0}$ of length at least $(\frac{n-3}{2})^{\log_{3}2}$,
which can be extended to a cycle $C$ in $G$ containing $P$ of length at least
$(\frac{n-3}{2})^{\log_{3}2}+3$. As $P$ is a zigzag-path, without loss of
generality, we may assume that there is precisely one face incident with $v$
lying in the exterior of $C$. Therefore, there are at most five faces incident
with $v$ lying in the interior of $C$. It follows from Lemma 2(ii) that there
is a $k$-cycle containing $P$ as $k\geq 7\geq|N_{G}(v)|+1$. This assures that
$\mathcal{C}^{k}_{P}\neq\emptyset$.

As $|\mathcal{P}|\in\Omega(n)$ and $\mathbf{O}_{\mathfrak{C}_{k}}\leq 5$,
applying the Counting Base Lemma to the counting base $\mathfrak{C}_{k}$
yields that there are $\Omega(n)$ $k$-cycles. ∎

For a given $n$-vertex triangulation $G$, the radius of $G^{*}$ is at least
logarithmic in $n$, but it can be linear: consider double wheels (i.e. the
join of $\overline{K_{2}}$ and a cycle), whose duals are prisms.

It follows from a series of papers that planar 4-connected graphs on $n$
vertices contain a $k$-cycle for every $k\in\\{n-7,\ldots,n\\}$; for details,
see [7]. Taking the proof technique of a work by Alahmadi, Aldred, and
Thomassen [1] into account, it is straightforward to infer the presence of an
exponential number of $k$-cycles in 5-connected triangulations on $n$ vertices
for every $k\in\\{n-7,\ldots,n\\}$. It remains an open question whether for
every 5-connected triangulation $G$ there exists a subset $S$ of the cycle
spectrum of $G$ such that $|S|\in\omega(1)$ and $G$ contains exponentially
many $k$-cycles for every $k\in S$.

##  3 Linearly many long cycles

As we have mentioned in the introduction, there are infinitely many $n$-vertex
triangulations with no $k$-cycle for all $k>9n^{\log_{3}2}$, see [19]. So in
the family of all triangulations the minimum number of hamiltonian cycles—and
indeed the minimum number of long cycles—is simply 0. However, it is a classic
problem to investigate how few hamiltonian cycles may occur if we impose the
presence of at least one hamiltonian cycle. (We point out that, from a more
general perspective, Alahmadi, Aldred, and Thomassen [1] observed that a
4-connected hamiltonian triangulation on any fixed surface may have at most
$O(n^{4})$ cycles.) In 1979, Hakimi, Schmeichel, and Thomassen showed that
there is an infinite family of triangulations with exactly four hamiltonian
cycles [10], and this is a lower bound for the minimum number of hamiltonian
cycles in any hamiltonian triangulation on at least 5 vertices [12]. This
motivates the following result; therein, we will make use of the function
$g:\mathbb{N}\rightarrow\mathbb{N}$,
$t\mapsto\left\lceil\frac{(t-3)(t-4)}{12}\right\rceil$ and, in contrast to all
other parts of this paper, not restrict ourselves to the spherical case.

######  Theorem 2.

Consider an integer $t\geq 4$ with $t=0,3,4,7$ mod. $12$, and let
$f:\mathbb{N}\rightarrow\mathbb{R}_{\geq 1}$ be a function such that there
exists an $n_{0}$ such that for all $n\geq n_{0}$ we have
$f(n)<\frac{n}{t}-1$. Then there exists an infinite family ${\cal G}$ of
hamiltonian triangulations of genus $g(t)$ such that every $G\in{\cal G}$ with
$n:=|V(G)|$ contains $O(f(n)^{2t-3})$ $k$-cycles for any $k\in\\{\lceil
n-f(n)\rceil,\ldots,n\\}$.

###### Proof.

Let $W$ be the join of $\overline{K_{2}}$ and a cycle $D$, i.e. a double
wheel. Let $vw\in E(D)$. $vw$ lies in the boundary of exactly two facial
triangles, $avw$ and $bvw$. We call $W-vw+ab$ a _flipped double wheel_ , and
$w$ its _apex_.

By the Map Colour Theorem of Ringel and Youngs [21] we can embed $K_{t}$ on a
surface of genus $g(t)$. Consider $G\cong K_{t}$; it is well-known that for
the given values of $t$, the embedding is a triangulation. We first treat the
case when $t=4$. Consider the infinite family of triangulations given in
Figure 1. It consists of a complete graph on four vertices $a,b,c,d$ with a
flipped double wheel inserted into each of its four triangles. We call these
triangles as well as the vertices $a,b,c,d$ _original_. We insert the same
number $p$ of vertices into each original triangle. We denote this graph by
$G_{p}$. Put $n:=|V(G_{p})|=4p+4$. Henceforth, we assume $p$ to be large;
moreover, the proof uses the embedding of $G_{p}$ given in Figure 1.

Figure 1: The plane graph $G_{p}$.

In $G_{p}$, consider a $k$-cycle $C$ with $k>3p+4$. For any fixed original
triangle $\Delta$, the cycle $C$ cannot exit ${\rm int}\Delta$ towards an
original vertex and then re-enter ${\rm int}\Delta$. Let $\Delta$ be an
original triangle with vertices $x,y,z$ such that $z$ is cubic in ${\rm
Int}\Delta$. Consider the path $P:=C\cap{\rm Int}\Delta$. Either $P$ is an
$xy$-path, in which case we call this traversal of $\Delta$ _flexible_ , or
$P$ is an $xz$\- or a $yz$-path, in which case we call this traversal _fixed_.
For any non-negative integer $q\leq p$, there are $O(q)$ flexible traversals
avoiding exactly $q+1$ vertices in ${\rm Int}\Delta$, and a constant number of
fixed traversals avoiding exactly $q+1$ vertices in ${\rm Int}\Delta$. As
$k>3p+4$, the cycle $C$ must visit the vertex $c$ (as defined in Figure 1) and
$ac,bc,cd\notin E(C)$, so at most two traversals of the interiors of original
triangles are flexible.

Let $\Delta_{1},\Delta_{2},\Delta_{3},\Delta_{4}$ be the four original
triangles of $G_{p}$. Put $q:=n-k$ and let $q_{i}$ denote the number of
vertices $C$ avoids in ${\rm int}\Delta_{i}$ so that
$q=q_{1}+q_{2}+q_{3}+q_{4}$. It is well-known that there are $\binom{q+3}{3}$
possible variations for $C$. We have shown above that a $k$-cycle $C$ with
$k>3p+4$ admits at most two flexible traversals, so that there are in total
$O(q^{5})$ cycles of length $n-q$ in $G_{p}$ for all $q<\frac{n}{4}-1$.

We now use the same strategy for the case when $t>4$. Consider $v\in V(G)$.
Insert into each of the $t-1$ triangular faces surrounding $v$ a flipped
double wheel on $p+3$ vertices such that its apex is identified with $v$.
Among the triangles sharing an edge with $G[N(v)]$ but not incident with $v$,
choose one arbitrarily and insert thereinto a flipped double wheel as well. We
call the resulting graph $G_{p}$. In $G_{p}$, consider a $k$-cycle $C$ with
$k>(t-1)p+t$. It is not difficult to see that among the $t$ flipped double
wheels present in $G_{p}$, at least two of $C$’s traversals of flipped double
wheels are fixed (as defined in the third paragraph of this proof). This
yields at most $t-2$ flexible traversals. Put $q:=n-k$. Arguing as above,
there are $\binom{q+t-1}{t-1}$ possibilities for $C$ to avoid $q$ vertices. We
obtain in total $O(q^{2t-3})$ cycles of length $n-q$ for all
$q<\frac{n}{t}-1$. ∎

One can infer immediately from the above result the following corollary.

######  Corollary 1.

For any non-negative integers $c,t$ there exists a constant $c^{\prime}>0$ and
an infinite family ${\cal G}$ of triangulations of genus $g(t)$ such that any
$G\in{\cal G}$ contains at least one and at most $c^{\prime}$ $k$-cycles for
any $k\in\\{\lceil n-c\rceil,\ldots,n\\}$. Furthermore, there exists an
infinite family ${\cal G}$ of triangulations of the sphere such that any
$G\in{\cal G}$ contains at least one and at most $O(n)$ many $k$-cycles for
any $k\in\\{\lceil n-\sqrt[5]{n}\rceil,\ldots,n\\}$, and an infinite family
${\cal G}^{\prime}$ of triangulations of the torus such that any $G\in{\cal
G}^{\prime}$ contains at least one and at most $O(n)$ many $k$-cycles for any
$k\in\\{\lceil n-\sqrt[11]{n}\rceil,\ldots,n\\}$.

We now discuss 4-connected triangulations and recall that by a classic theorem
of Whitney [26], these form a subclass of the family of all hamiltonian
triangulations. Alahmadi, Aldred, and Thomassen [1] showed that every
5-connected triangulation has exponentially many hamiltonian cycles. Lo and
Qian [17] extended this result by proving that every 4-connected triangulation
with $O(n)$ many 4-cuts has exponentially many hamiltonian cycles. For an
integer $n\geq 5$, the join $G$ of $C_{n-2}$ and $\overline{K}_{2}$—the so-
called _double wheel_ , which is 4-connected—satisfies $c_{3}(G)\in\Theta(n)$
and $c_{k}(G)\in\Theta(n^{2})$ for all $k\geq 4$; here, for a given graph $G$,
we denote by $c_{k}(G)$ the number of $k$-cycles occurring in $G$. We
emphasise that thus, perhaps contrary to intuition, in 4-connected
triangulations no better solution to Problem 1 than a quadratic one can be
achieved. Double wheels have $\Theta(n^{2})$ 4-cuts, and no 4-connected
triangulation with fewer hamiltonian cycles than a double wheel is known.
Indeed, Hakimi, Schmeichel, and Thomassen [10] conjecture that every
4-connected $n$-vertex triangulation $G$ has at least $2(n-2)(n-4)$
hamiltonian cycles333Very recently, this conjecture has been solved
_asymptotically_ , see [14]., with equality if and only if $G$ is a double
wheel. As already pointed out by Lo and Qian, it is intriguing to observe that
few 4-cuts seem to imply many hamiltonian cycles, and vice-versa.

The next theorem’s first part answers Problem 2 affirmatively, while its
second part proves that, under certain circumstances, 4-connected
triangulations contain a quadratic number of $k$-cycles for many values of
$k$. We emphasise here the important open problem to determine whether there
exists a $k$ such that every $n$-vertex triangulation contains $\Omega(n^{2})$
$k$-cycles.

######  Theorem 3.

  1. (i)

Every $n$-vertex triangulation with at most one separating triangle contains
$\Omega(n)$ $k$-cycles for every $k\in\\{3,\ldots,n\\}$.

  2. (ii)

Let $G$ be a $4$-connected $n$-vertex triangulation. Suppose there is a set
${\cal S}$ of separating $4$-cycles in $G$ with

$\iota:=\big{|}\\{(C,C^{\prime})\in{\cal S\times\cal S}:C\cap C^{\prime}\cong
K_{2}\\}\big{|}.$

Then $G$ contains $\Omega(|\mathcal{S}|/(\iota+1))$ $k$-cycles for every
$k\in\\{\lceil\frac{n}{2}+\sqrt{\frac{n}{2}-2}\rceil+2,\ldots,n\\}$.

###### Proof.

(i) First, assume that $7\leq k\leq n$. Let $G$ be a triangulation on $n$
vertices. For any edge $uv$ in $G$, there are exactly two vertices
$w_{1},w_{2}$ such that $\\{u,v,w_{1}\\}$ and $\\{u,v,w_{2}\\}$ induce
triangular faces in $G$. We call $w_{1}uvw_{2}$ and $w_{1}vuw_{2}$ _zigzag-
paths_ with _internal vertices_ $u,v$. We may identify a zigzag-path with its
edge set, and define $\mathcal{P}$ to be the set of zigzag-paths that have all
internal vertices of degree at least 4 and at least one internal vertex of
degree at most 6. As $G$ has at most one cubic vertex and average degree less
than 6, we have that $|\mathcal{P}|\in\Omega(n)$. For any $P\in\mathcal{P}$,
we define $\mathcal{C}^{k}_{P}$ to be the family of $k$-cycles $C$ with
$E(C)\supset P$ and $\sigma(P):=w_{1}vuw_{2}$ when $P=w_{1}uvw_{2}$.

We claim that
$\mathfrak{C}_{k}=(\mathcal{P},\\{\mathcal{C}^{k}_{P}\\}_{P\in\mathcal{P}},\sigma)$
is a counting base. It is left to show that every element of $\mathcal{P}$ can
be extended to a cycle of length $k$ for any given $k\geq 7$.

Let $k$ be an integer satisfying $7\leq k\leq n$. We now show that
$\mathcal{C}^{k}_{P}$ is non-empty for every $P\in\mathcal{P}$. By [5, Lemma
14(i)] there is a hamiltonian cycle $\mathfrak{h}$ in $G$ that contains $P$.
Denote by $v$ an internal vertex of $P$ of degree at most 6. As $P$ is a
zigzag-path, without loss of generality, we may assume that there is precisely
one face incident with $v$ lying in the exterior of $\mathfrak{h}$. Therefore,
there are at most five faces incident with $v$ lying in the interior of
$\mathfrak{h}$. It follows from Lemma 2(ii) that there is a $k$-cycle
containing $P$ in ${\rm Int}\mathfrak{h}$ as $k\geq 7\geq|N_{G}(v)|+1$. Hence
we conclude that $\mathcal{C}^{k}_{P}\neq\emptyset$.

As $|\mathcal{P}|\in\Omega(n)$ and $\mathbf{O}_{\mathfrak{C}_{k}}\leq 5$, we
resolve Problem 2 for $k\geq 7$ by applying the Counting Base Lemma to the
counting base $\mathfrak{C}_{k}$. As already mentioned in the proof of Theorem
3, for $k\in\\{3,4,5\\}$ we get a linear lower bound on the number of
$k$-cycles by Euler’s formula and results of Hakimi and Schmeichel [9], while
the case $k=6$ follows from Theorem .

(ii) In this part, we define $\mathcal{P}$ to be the set of pairs of
independent edges in 4-cycles from $\mathcal{S}$, i.e. for any
$P\in\mathcal{P}$, there exists a 4-cycle
$v_{1}v_{2}v_{3}v_{4}v_{1}\in\mathcal{S}$ such that
$P=\\{v_{1}v_{2},v_{3}v_{4}\\}$. Furthermore, we define
$\sigma(P):=\\{v_{1}v_{4},v_{2}v_{3}\\}$ and $\mathcal{C}^{k}_{P}$ to be the
family of $k$-cycles $C$ satisfying that $P\subset E(C)$ and $C-P$ is the
union of a $v_{1}v_{3}$-path and a $v_{2}v_{4}$-path. To show that
$\mathfrak{C}_{k}:=(\mathcal{P},\\{\mathcal{C}^{k}_{P}\\}_{P\in\mathcal{P}},\sigma)$
is a counting base, it is left to verify that $\mathcal{C}^{k}_{P}$ is non-
empty.

Let $P\in\mathcal{P}$ with $P=\\{v_{1}v_{2},v_{3}v_{4}\\}$ and
$C=v_{1}v_{2}v_{3}v_{4}v_{1}\in{\cal S}$. Without loss of generality we assume
that $|{\rm int}C|\leq\frac{n}{2}-2$. Put $j:=|{\rm ext}C|\geq\frac{n}{2}-2$,
$d_{1}:=d_{{\rm Ext}C-v_{2}-v_{4}}(v_{1},v_{3})$, and $d_{2}:=d_{{\rm
Ext}C-v_{1}-v_{3}}(v_{2},v_{4})$. We claim that $(d_{1}-1)(d_{2}-1)\leq j$.
Denote by $L_{i}$ the set of vertices of ${\rm Ext}C-v_{2}-v_{4}$ at distance
$i$ from $v_{1}$. It is not difficult to see that for any
$i\in\\{1,\dots,d_{1}-1\\}$ there is a path $P^{i}$ in the graph induced by
$L_{i}$ with one end-vertex in $N(v_{2})$ and one other in $N(v_{4})$ (here we
include the case that $P^{i}$ consists of only one vertex which is in
$N(v_{2})\cap N(v_{4})$). Note that $P^{i}$ has length at least $d_{2}-2$.
Thus $j\geq\sum_{i=1}^{d_{1}-1}|L_{i}|\geq(d_{1}-1)(d_{2}-1)$, from which we
obtain that $d_{1}\leq\sqrt{j}+1$ or $d_{2}\leq\sqrt{j}+1$; without loss of
generality assume the former holds.

By the theorem of Thomas and Yu [24] stating that in a planar 4-connected
graph the removal of any pair of vertices yields a hamiltonian graph, ${\rm
Ext}C-v_{2}-v_{4}$ contains a hamiltonian $v_{1}v_{3}$-path. By applying Lemma
2(i) to a $(d_{1}+2)$-cycle containing $v_{1}v_{2}v_{3}$ and to a
$(j+3)$-cycle containing $v_{1}v_{2}v_{3}$ in ${\rm Ext}C-v_{4}$,
respectively, we obtain that ${\rm Ext}C-v_{2}-v_{4}$ contains a
$v_{1}v_{3}$-path of length $k$ for every integer $k$ satisfying
$\sqrt{j}+1\leq k\leq j+1$. Once more invoking the aforementioned theorem of
Thomas and Yu, we know that there exists a hamiltonian $v_{2}v_{4}$-path in
${\rm Int}C-v_{1}-v_{3}$. As a cycle can be obtained by adding edges
$v_{1}v_{2},v_{3}v_{4}$ to the union of a $v_{1}v_{3}$-path in ${\rm
Ext}C-v_{2}-v_{4}$ and a $v_{2}v_{4}$-path in ${\rm Int}C-v_{1}-v_{3}$, for
every integer $k$ satisfying $\frac{n}{2}+\sqrt{\frac{n}{2}-2}+2\leq k\leq n$
we have that $\mathcal{C}^{k}_{P}\neq\emptyset$ for every $P\in\mathcal{P}$.
We can conclude that for these $k$, the triple
$\mathfrak{C}_{k}=(\mathcal{P},\\{\mathcal{C}^{k}_{P}\\}_{P\in\mathcal{P}},\sigma)$
is a counting base.

Note that $|\mathcal{P}|=2|\mathcal{S}|$ and
$\mathbf{O}_{\mathfrak{C}_{k}}\leq\iota+1$. We complete the proof by applying
the Counting Base Lemma to the counting base $\mathfrak{C}_{k}$. ∎

If there are two vertices having $t$ common neighbours, then there is a set
${\cal S}$ of separating $4$-cycles with $|\mathcal{S}|\in\Omega(t^{2})$ and
$\iota:=|\\{(C,C^{\prime})\in{\cal S\times\cal S}:C\cap C^{\prime}\cong
K_{2}\\}|=0$. This yields the following corollary of Theorem 3(ii).

######  Corollary 2.

Every $4$-connected $n$-vertex triangulation with two vertices having
$\Theta(n)$ common neighbours contains $\Omega(n^{2})$ $k$-cycles for every
$k\in\\{\lceil\frac{n}{2}+\sqrt{\frac{n}{2}-2}\rceil+2,\ldots,n\\}$.

For every integer $k\geq 4$, Theorem 3(i) is not true for triangulations with
$k$ separating triangles as there exist infinite families of such
triangulations with a constant number of hamiltonian cycles; for
$k\in\\{4,5\\}$ see [3], and for $k\geq 6$, infinitely many non-hamiltonian
examples are easy to describe using toughness arguments. We do not know
whether Theorem 3(i) can be extended to all triangulations containing at most
two or at most three separating triangles.

We conclude this section with an application of Theorem 3(i) to general (i.e.
not necessarily 4-connected) triangulations.

######  Corollary 3.

Let $G$ be an $n$-vertex triangulation containing a triangle $\Delta$ such
that ${\rm Int}\Delta$ is a triangulation containing at most one separating
triangle and $\Theta(n)$ vertices. Then $G$ contains $\Omega(n)$ many
$k$-cycles for all $k\in\\{3,\ldots,|V({\rm Int}\Delta)|\\}$.

##  4 Notes

1. It remains an open question whether there exists a $k$ such that every $n$-vertex triangulation contains $\Omega(n^{2})$ many $k$-cycles. We do know by Theorem 3(ii) and Corollary 2 that under certain conditions 4-connected $n$-vertex triangulations contain $\Omega(n^{2})$ $k$-cycles for many values of $k$, and that _every_ such triangulation contains $\Omega(n^{2})$ many $(n-2)$-cycles by a theorem of Thomas and Yu [24], and $\Omega(n^{2})$ many $n$-cycles by a very recent breakthrough result of Liu, Wang, and Yu [14]. Although not explicitly stated, the latter work also implies the presence of $\Omega(n^{2})$ many $(n-1)$-cycles in 4-connected $n$-vertex triangulations.

2. As mentioned in the introduction, Mohar and Shantanam [18] showed that in an 4-connected $n$-vertex triangulation $G$, every edge in $G$ is contained in a $k$-cycle for every $k\in\\{3,\ldots,n\\}$. It would be interesting to investigate to which degree this can be strengthened in an enumerative sense. While there are always exactly two 3-cycles through any given edge, already for 4-cycles the situation is more diverse: any edge in any triangulation on at least five vertices lies on at least four 4-cycles, but there exist triangulations such as the double wheels in which many edges lie on a linear (in the graph’s order) number of 4-cycles. Furthermore, there exists a length $k$, depending on $n$, for which we can guarantee that every edge in every 4-connected triangulation lies in an at least linear number of $k$-cycles: it follows from a result of Ozeki and Vrána [20] that, given a planar 4-connected graph $G$, for any 2-element set $X\subset E(G)\cup E(\overline{G})$, the graph $G\cup X$ admits a hamiltonian cycle containing $X$. Thus, for any pairwise distinct $v,w_{1},w_{2}\in V(G)$, where $w_{1}$ and $w_{2}$ are adjacent, we obtain a hamiltonian cycle in $G-v$ passing through $w_{1}w_{2}$. Hence, for any $n$-vertex planar 4-connected graph $G$ and any edge $e$ therein, $G$ contains $\Omega(n)$ many $(n-1)$-cycles containing $e$. In fact, double wheels show that one cannot do better than a linear bound for $(n-1)$-cycles through a specific edge.

3. In analogy to Tutte’s celebrated result that planar 4-connected graphs are hamiltonian [25], one can ask how the problems and conjectures in this paper relate to the larger family of planar 4-connected graphs. While this class is known to contain $\Omega(n)$ hamiltonian cycles [4], in stark contrast to 4-connected triangulations, some of its members are not even pancyclic, as 4-cycles might not be present (consider the line-graph of the dodecahedron).

Acknowledgements. On-Hei Solomon Lo’s work was partially supported by Natural
Sciences and Engineering Research Council of Canada (NSERC). Carol T.
Zamfirescu’s research was supported by a Postdoctoral Fellowship of the
Research Foundation Flanders (FWO).

## References

  * [1] A. Alahmadi, R. E. L. Aldred, and C. Thomassen. Cycles in 5-connected triangulations. _J. Combin. Theory, Ser. B_ 140 (2020) 27–44.
  * [2] A. F. Alameddine. On the number of cycles of length 4 in a maximal planar graph _J. Graph Theory_ 4 (1980) 417–422.
  * [3] G. Brinkmann, J. Souffriau, and N. Van Cleemput. On the number of hamiltonian cycles in triangulations with few separating triangles. _J. Graph Theory_ 87 (2018) 164–175.
  * [4] G. Brinkmann and N. Van Cleemput. 4-connected polyhedra have at least a linear number of hamiltonian cycles. _Europ. J. Combin._ 97 (2021) Article number 103395.
  * [5] G. Brinkmann and C. T. Zamfirescu. Polyhedra with few 3-cuts are hamiltonian. _Electron. J. Combin._ 26 (2019) #P39.
  * [6] G. Chen and X. Yu. Long cycles in 3-connected graphs. _J. Combin. Theory, Ser. B_ 86 (2002) 80–99.
  * [7] Q. Cui, Y. Hu, and J. Wang. Long cycles in 4-connected planar graphs. _Discrete Math._ 309 (2009) 1051–1059.
  * [8] E. Győri, A. Paulos, N. Salia, C. Tompkins, and O. Zamora. The Maximum Number of Pentagons in a Planar Graph. arXiv:1909.13532 [math.CO].
  * [9] S. L. Hakimi and E. F. Schmeichel. On the Number of Cycles of Length $k$ in a Maximal Planar Graph. _J. Graph Theory_ 3 (1979) 69–86.
  * [10] S. L. Hakimi, E. F. Schmeichel, and C. Thomassen. On the Number of Hamiltonian Cycles in a Maximal Planar Graph. _J. Graph Theory_ 3 (1979) 365–370.
  * [11] T. Huynh, G. Joret, and D. R. Wood. Subgraph densities in a surface. arXiv:2003.13777 [math.CO]. Published online in _Combinatorics, Probabiliy, and Computing_ , see https://doi.org/10.1017/S0963548321000560.
  * [12] J. Kratochvil and D. Zeps. On the number of Hamiltonian cycles in triangulations. _J. Graph Theory_ 12 (1988) 191–194.
  * [13] X. Liu and X. Yu. Number of Hamiltonian Cycles in Planar Triangulations. _SIAM J. Discrete Math._ 35 (2021) 1005–1021.
  * [14] X. Liu, Z. Wang, and X. Yu. Counting Hamiltonian cycles in planar triangulations. _J. Combin. Theory, Ser. B_ 155 (2022) 256–277.
  * [15] O.-H. S. Lo. Hamiltonian cycles in 4-connected plane triangulations with few 4-separators. _Discrete Math._ 343 (2020) Article Nr. 112126.
  * [16] O.-H. S. Lo. Distribution of subtree sums. To appear in _Europ. J. Combin._
  * [17] O.-H. S. Lo and J. Qian. Hamiltonian cycles in 4-connected planar and projective planar triangulations with few 4-separators. _SIAM J. Discrete Math._ 36 (2022) 1496–1501.
  * [18] B. Mohar and A. Shantanam. Pancyclicity in 4-connected planar graphs. Manuscript.
  * [19] J. W. Moon and L. Moser. Simple paths on polyhedra. _Pacific J. Math._ 13 (1963) 629–631.
  * [20] K. Ozeki and P. Vrána. 2-edge-Hamiltonian-connectedness of 4-connected plane graphs. _Europ. J. Combin._ 35 (2014) 432–448.
  * [21] G. Ringel and J. W. T. Youngs. Solution of the Heawood map-coloring problem. _Proc. Nat. Acad. Sci._ 60 (1968) 438–445.
  * [22] D. P. Sanders. On Hamiltonian cycles in certain planar graphs. _J. Graph Theory_ 21 (1996) 43–50.
  * [23] L. Sheppardson and X. Yu. Long cycles in 3-connected graphs in orientable surfaces. _J. Graph Theory_ 41 (2002) 69–84.
  * [24] R. Thomas and X. Yu. 4-Connected Projective-Planar Graphs are Hamiltonian. _J. Combin. Theory, Ser. B_ 62 (1994) 114–132.
  * [25] W. T. Tutte. A theorem on planar graphs. _Trans. Amer. Math. Soc._ 82 (1956) 99–116.
  * [26] H. Whitney. A theorem on graphs. _Ann. Math._ 32 (1931) 378–390.