On the Size of k-Irreducible Triangulations

Our proof of Theorem 1 is actually a consequence of a stronger result on system of curves that we introduce now. We investigate $k$-irreducible triangulations from the powerful perspective initiated by (de Graaf and) Schrijver in a series of papers (see e.g., [39, 40, 19, 20]), which consists in encoding the metric structure of an embedded graph using a system of curves. Note that this approach was already implicit in Steinitz’s proof of his aforementioned theorem, as explained in Chang [10].

For the case of $k$-irreducible triangulations, this is done as follows. One first observes that instead of considering shortest non-contractible closed walks, one could consider instead shortest non-contractible closed curves crossing the triangulation exactly at the vertices. Such curves are commonly called nooses in structural graph theory. If one defines the length of those curves as this number of intersections, one sees that any non-contractible closed walk in a triangulation can be deformed to a non-contractible noose of the same length and vice-versa, see Figure 1, left. The length of a shortest non-contractible noose is called the face-width (also called representativity in, e.g. [25]), and therefore we can equivalently define $k$-irreducibility as having face-width at least $k$ and being irreducible for this property.

The medial graph $M$ of a triangulation $T$ of a surface $S$ is the embedded graph in $S$ which has a vertex in the middle of each edge of $T$ and in each face $f$ of $T$ we add edges between vertices of $M$ that belong to consecutive edges of $f$. See Figure 1, right for an illustration. Note that $M$ is a simple face-bipartite $4$-regular graph and that the length of a noose $c$ for $T$ is equal to half the number of transverse intersections it has with $M$. Because $M$ is $4$-regular, it can be considered as a system of curves $𝒞=(c_1,\mathrm{\dots },c_n)$. The crossing number of a system of curves $𝒞$, denoted by $\mathrm{cr}(𝒞)$ is its number of intersections. The length of a curve $c$ with respect to $𝒞$ is the number of intersections of $c$ and $𝒞$, denoted by $\mathrm{cr}(c,𝒞)$.

The strength of this perspective is that this allows to understand metric deformations of $T$ (e.g., edge contractions) under the lens of topological deformations (homotopies) of $𝒞$. For instance, it follows from the work of Schrijver [40] that on an orientable surface, the system of curves corresponding to a minor-minimal graph of face-width $k$ is necessarily in minimal position: it contains no contractible curves and its crossing number $\mathrm{cr}(𝒞)$ is minimized over all families ${𝒞}^{\prime }$ homotopic to $𝒞$ (we refer to Section 2 for the background on homotopies and a precise statement of Theorem 4 by Schrijver).

A smoothing of a system of curves $𝒞$ is the system of curves obtained from $𝒞$ by removing a vertex $v$ and reconnecting the incident strands in one of two ways as in Figure 2. Note that a smoothing may change the number of components.

A system of curves $𝒞$ on a surface $S$ is a $k$-irreducible system of curves for some $k⩾1$ if it is connected and:

• $\mathrm{■}$

  Every non-contractible closed curve $c$ on $S$ transverse to $𝒞$ satisfies $\mathrm{cr}(c,𝒞)⩾k$, and

• $\mathrm{■}$

  for every system of curves ${𝒞}^{\prime }$ obtained by a smoothing of $𝒞$, there is a non-contractible closed curve $c$ such that .

Finally, a system of curves on a surface is face-bipartite if there is a $2$-coloration of its faces (connected components of the complement) such that any two adjacent faces have different colors. We now have all the ingredients to state our second theorem.

Theorems 1 and 2 provide discrete counterparts to results in systolic geometry. This subfield of differential geometry investigates topological spaces endowed with continuous metrics (typically Riemannian) and aims at understanding the structure and properties of their shortest non-contractible curves, called systoles. We refer to the book of Katz [31] for an introduction.

The famed systolic inequality of Gromov [26] states that for any surface of genus $g$ and area $A$, the systole has length $O(\sqrt{A/g}\log g)$. This is known to be tight: Brooks [8] and Buser and Sarnak [9] provided families of hyperbolic surfaces achieving this bound. There are discrete analogues of these results for embedded graphs [28, 16, 33], showing that the edge-width of a triangulation with $n$ triangles is similarly bounded by $O(\sqrt{n/g}\log g)$ and that this is asymptotically tight. Equivalently, this shows that any triangulation of edge-width $k$ has $\mathrm{\Omega }(k^{2}g/{\log }^{2}g)$ triangles¹¹1Note that the growth is sensibly different if one considers the number of vertices instead of the number of triangles, see Melzer [36, Section 2.2]. Bounding the size of $k$-irreducible triangulations then amounts to looking for a reverse systolic inequality, bounding how far from this lower bound a locally extremal object for the systolic inequality can be. From this perspective, it is noteworthy that the logarithmic factor, which is known to be required for the systolic inequality, disappears in our bounds in Theorems 1 and 2, even though our bounds are also tight.

We are not aware of any works investigating continuous versions of such a reverse systolic inequality. One difficulty is that the space of Riemannian metrics on a surface is not compact, and extremal surfaces for the systolic inequality in negative Euler characteristic are expected to exhibit singularities, see for example Gromov [26, pp.62-65]. This can be addressed by adding additional assumptions on the curvature, restricting to hyperbolic surfaces as in Fortier Bourque and Rafi [7], or nonpositively curved surfaces as in Katz and Sabourau [32]. Since the discrete setting of triangulations does not suffer from these analytic issues, it provides a convenient testbed for the study of locally extremal surfaces. The framework of geodesic currents of Bonahon [5] could provide an interesting middle-ground between these two worlds, keeping a continuous flavour but with strong compactness properties.

Many articles in computational geometry in the last twenty years have been targeted at understanding topologically meaningful curves on surfaces, from the perspectives of both algorithms and combinatorics. We refer to the dedicated chapter by Éric Colin de Verdière in the handbook of computational geometry [15] for a survey of this active field of research. Our proof techniques deal specifically with families of curves in minimal position on surfaces, a problem for which polynomial-time algorithms have been recently provided by Chang and de Mesmay [12], and Dubois [23]. The study of systolic properties of surfaces through the lens of such systems of curves has been instrumental in recent works of Cossarini [17] and Cossarini and Sabourau [18]. The medial graph construction connects homotopy of curves with electrical moves, as studied in Chang and Erickson [13], Chang, Cossarini and Erickson [11] and Aranguri, Chang and Fridman [1]. Very recently, Delecroix, Fontaine and Lazarus [22] have made algorithmic Schrijver’s concept of kernel [40], which generalizes our $k$-irreducible triangulations to metric structures which are extremal with respect to the entire set of lengths of non-contractible curves (the length spectrum).

After some preliminaries in Section 2, we first explain how Theorem 2 implies Theorem 1 in Section 3. Then the main ingredient is Proposition 7 proven in Section 4. Namely given a $k$-irreducible system of curves, it shows the existence of $O(g)$ curves of length at most $2k$ filling $S$. This immediately yields a first bound (Theorem 13), albeit one not linear in $g$. Section 5 introduces additional combinatorial tools to obtain the tight bound of Theorem 2. Due to line restrictions, some proofs are deferred to the full version [21], which provides slightly more general results and a treatment of one case of non-orientable surface.

Let us denote as before by $G$ an (edge inclusion-wise) minimal subgraph of $T$ such that the length of a shortest non-contractible noose on $G$ is still $k$, and by $𝒞$ the system of curves associated to $G$. As $\mathrm{cr}(c,G)⩾k$ for every non-contractible curve $c$, $\mathrm{cr}(\gamma ,𝒞)=2\mathrm{cr}(\gamma ,G)⩾2k$ for every non-trivial homotopy class $\gamma$.

Let ${𝒞}^{\prime }$ be a smoothing of $𝒞$. As shown in [40], a smoothing of $𝒞$ either corresponds to an edge deletion or an edge contraction in $G$. We work separately on these two cases.

1. 1.

   Assume that ${𝒞}^{\prime }$ is obtained from $𝒞$ by a smoothing corresponding to deleting the edge $e$. Let $G^{\prime }=G\setminus \{e\}$. Then by definition of $G$, there is a non-contractible curve $c$ such that . Thus where $\gamma$ is the homotopy class of $c$.

2. 2.

   Assume that ${𝒞}^{\prime }$ is obtained from $𝒞$ by a smoothing corresponding to contracting the edge $e=(uv)$. As $T$ is a $k$-irreducible triangulation, there is a systole $c$ of $T$ going through $u$ and $v$ consecutively. Thus this systole is also a systole of $G$ with the same property and is also a systole of $𝒞$ crossing two consecutive edges of $𝒞$ around the vertex $v(e)$ (see Figure 4). Thus, the smoothing reduces the length of $c$ and where $\gamma$ denotes the homotopy class of $c$.

Since $G$ is connected, so is $𝒞$. Therefore the system of curves $𝒞$ is $2k$-irreducible. It follows from Theorem 4 that it is in minimal position. Finally, it is face-bipartite by construction: the faces of the medial graph are either faces or vertices of $T$. $◀$

We are now ready to prove Theorem 1 assuming Theorem 2. We restate it for convenience.

As before, let $G$ be a minimal subgraph of $T$ such that the length of a shortest non-contractible noose on $G$ is $k$, and let $𝒞$ be its associated system of curves. By Proposition 6, any system of curves associated to $T$ is a $2k$-irreducible system of curves. Thus by Theorem 2, the crossing number $\mathrm{cr}(𝒞)$ of $𝒞$ is at most $120{(2k)}^{2}g=480k^{2}g$.

Now let $M$ be the medial graph of $G$ from which is built the system of curves $𝒞$. It is such that $|V(M)|=\mathrm{cr}(𝒞)$ and because it is quartic $|E(M)|=2\mathrm{cr}((C))$. The graph $M$ is face bipartite and the classes of the bipartition are in bijection with the vertices $V(G)$ and the faces $F(G)$ of $G$. These bijections preserve the degree and hence ${\displaystyle \sum _{v\in V(G)}}{\mathrm{deg}}_G(v)=|E(M)|=2\mathrm{cr}(𝒞)$. Now, by Proposition 6, $𝒞$ is in minimal position. In particular, $𝒞$ has neither monogon nor bigon. In other words, each face of $M$ has degree at least $3$. Thus ${\displaystyle \sum _{v\in V(G)}}{\mathrm{deg}}_G(v)⩾3|V(G)|$. We conclude that $|V(T)|=|V(G)|⩽{\displaystyle \frac{2}{3}}\mathrm{cr}(𝒞)⩽{\displaystyle \frac{2}{3}}480k^{2}g=320k^{2}g$, and $|E(T)|⩽3|V(T)|+6g-6⩽966k^{2}g$. $◀$

We first observe that we can assume that $k$ is even. Indeed, if this is not the case, since $𝒞$ is $k$-irreducible and face-bipartite, $𝒞$ is $(k-1)$-irreducible. We will build a set of curves of lengths at most $2k$ made of systoles and some curves that are obtained by concatenation of two systoles, and then show that these curves are filling.

The following claim is standard in geometry of curves on surfaces. As it is used many times throughout our proof, we provide a standalone proof.

Assume that the lift $\tilde{c}$ has a self-intersection. Then it forms a monogon: there is a disk in $\tilde{S}$ bounded by a subline of $\tilde{c}$. By homotopy, one can remove this monogon contradicting the fact that $c$ was in minimal position on $S$. Therefore, $\tilde{c}$ and $\widetilde{c^{\prime }}$ are lines in $\tilde{S}$.

Let us assume for contradiction that two lifts $\tilde{c}$ and $\widetilde{c^{\prime }}$ intersect twice. Then, since $\tilde{S}$ is contractible, they form a bigon: there is a disk in $\tilde{S}$ bounded by one subline $\alpha$ of $\widetilde{c^{\prime }}$ and one subline $\beta$ of $\tilde{c}$. Now, the homotopy moving $\alpha$ to $\beta$ projects to a homotopy on the surface, and leads to a new pair of curves intersecting less. This contradicts the hypothesis that $c$ and $c^{\prime }$ were in minimal position. $\mathrm{⊲}$

The next claim is the first step in defining the systoles we will work with.

Let ${𝒞}^{\prime }$ be the system of curves obtained by smoothing $v$ and connecting $e$ with $e^{\prime }$. As $𝒞$ is a $k$-irreducible system, there is a non-contractible curve $c$ in minimal position with respect to both $𝒞$ and ${𝒞}^{\prime }$ and such that . Since $𝒞$ and ${𝒞}^{\prime }$ differ from each other only at $v$, the curve $c$ goes from $e$ to $e^{\prime }$ in a neighborhood of $v$. If we pick $c$ with the property that and $\mathrm{cr}(c,𝒞)$ minimal, then it passes only once consecutively through $e$ and $e^{\prime }$ and $\mathrm{cr}(c,{𝒞}^{\prime })=\mathrm{cr}(c,𝒞)-2$.

As $𝒞$ is face-bipartite, all crossing numbers of curves with respect to $𝒞$ are even. Since $k$ is even, we must have $\mathrm{cr}(c,{𝒞}^{\prime })=k-2$ and $\mathrm{cr}(c,𝒞)=k$. The curve $c$ is therefore a systole, this concludes the proof of the claim. $\mathrm{⊲}$

Let $e_1,e_2,e_3$ and $e_4$ be the four consecutive edges around a vertex $v$ of $𝒞$. By Claim 9 there is a systole $s_1$ crossing consecutively $e_1$ and $e_2$. Similarly, there is a systole $s_2$ crossing consecutively $e_2$ and $e_3$. We denote by $𝒮$ a set of curves containing a pair of such systoles $s_1$ and $s_2$ for each vertex of $𝒞$. Note that by definition a systole is in minimal position with respect to $𝒞$.

We first handle the case where the surface is a torus.

The proof is provided in the full version [21]. Since on a torus, any pair of curves intersecting essentially is filling, Claim 10 concludes the proof for the torus with the family $𝒮$. In the rest of the proof we assume that the surface has negative Euler characteristic. Therefore its universal cover is homeomorphic to an open disk and can be endowed with a boundary at infinity $\partial \tilde{S}$ which is a circle. The lifts of curves in $\tilde{S}$ are lines with endpoints on this boundary, and two curves are homotopic if and only if there exists lifts of the two curves having the same endpoints. Furthermore, no two lifts have exactly one endpoint in common. We refer to [24, Section 1].

We now define curves obtained by concatenations of two systoles. They will be used to fill the surface $S$. Let $s$ and $s^{\prime }$ be two systoles in $𝒮$ that start in the same face $f$ of $𝒞$ and such that $𝒞\cup \{s,s^{\prime }\}$ is in minimal position. Up to homotopy we can further assume that the first crossings with the boundary of $f$ occurs for both $s$ and $s^{\prime }$ at time $\pm \epsilon$ and that $s$ and $s^{\prime }$ do not intersect in this initial face. Namely $s([-\epsilon ,\epsilon ])\cap s^{\prime }([-\epsilon ,\epsilon ])=\mathrm{\varnothing }$ and that the points $s(\epsilon )$, $s(-\epsilon )$, $s^{\prime }(-\epsilon )$ and $s^{\prime }(\epsilon )$ appear on the boundary of $f$ in that counterclockwise order. Let $a$ and $a^{\prime }$ be arcs in the face $f$ that are in minimal position and go respectively from $s^{\prime }(-\epsilon )$ to $s(\epsilon )$ and $s(-\epsilon )$ to $s^{\prime }(\epsilon )$. These two arcs intersect exactly once. We define a new curve $t$ by the concatenation $t:={{a\cdot s|}_{[\epsilon ,-\epsilon ]}\cdot a^{\prime }\cdot s^{\prime }|}_{[\epsilon ,-\epsilon ]}$, see Figure 5. We say that $t$ is obtained by wedding $s$ and $s^{\prime }$ if $t$ is in minimal position with respect to itself. Equivalently, we can make a wedding if in the universal cover $\tilde{S}$ of $S$ the two lifts of $s$ and $s^{\prime }$ starting from the same lift $\tilde{f}$ of $f$ do not intersect. By definition, a wedding has length $2k$ with respect to $𝒞$. If such a wedding is put in minimal position with respect to $𝒞$ by a homotopy, it might even get shorter.

We define the set ${𝒮}_2$ to be a set of representatives of the homotopy classes of all possible weddings of systoles in $𝒮$ such that $𝒞\cup 𝒮\cup {𝒮}_2$ is in minimal position. The following claim proves that the curves in $𝒮\cup {𝒮}_2$ intersect every possible simple closed curve on the surface.

We first put $c$ in minimal position with respect to $𝒞\cup 𝒮\cup {𝒮}_2$. Since $𝒞$ is filling, there is an edge $e=(uv)$ of $𝒞$ that intersects $c$. Let $c_1$ be the curve of $𝒞$ containing the edge $e$ and $c_2$ and $c_3$ be the curve crossing $c_1$ at $u$ and $v$ respectively. We denote by $s_1$ and $s_2$ the two systoles in $𝒮$ corresponding to $u$ and by $s_3$ and $s_4$ the ones corresponding to $v$. We will prove that $c$ intersects either $s_1$, $s_2$, $s_3$, $s_4$ or one of their pairwise weddings.

In the universal cover, our local picture lifts as in Figure 6, yielding lines $\widetilde{c_1}$, $\widetilde{c_2}$, $\widetilde{c_3}$, $\widetilde{s_1}$, $\widetilde{s_2}$, $\widetilde{s_3}$, $\widetilde{s_4}$ and $\tilde{c}$. The lines $\widetilde{c_1}$,$\widetilde{c_2}$, $\widetilde{c_3}$ intersect pairwise at most once and are simple because $𝒞$ is in minimal position. We do a case by case analysis depending on the topology of $\widetilde{c_2}$ and $\widetilde{c_3}$. The only ingredient we use is the fact that each pair of these curves intersect at most once.

If $\widetilde{c_2}$ and $\widetilde{c_3}$ intersect, then it is immediate that $\tilde{c}$ intersects at least one of the curves $\widetilde{s_1}$, $\widetilde{s_2}$, $\widetilde{s_3}$ or $\widetilde{s_4}$, see top left Figure 6. The same happens if $c_2$ and $c_3$ are homotopic since in that case $\widetilde{c_2}$ and $\widetilde{c_3}$ have the same endpoints in $\partial \tilde{S}$. Since these intersections are forced by the endpoints on $\partial \tilde{S}$ and homotopies do not move these endpoints, these intersections on $\tilde{S}$ project to essential intersections on $S$. See top right Figure 6.

The last case is if $\widetilde{c_2}$ and $\widetilde{c_3}$ are disjoint (including at their endpoints) as in bottom Figure 6. Then the wedding $w$ of $s_1$ and $s_4$ based at the added crossing lifts to two lines $\widetilde{w_1}$ and $\widetilde{w_2}$ which cross the lines $\widetilde{c_1}$ and $\widetilde{c_2}$, respectively $\widetilde{c_2}$ and $\widetilde{c_3}$ the same way that $\widetilde{s_1}$ and $\widetilde{s_4}$ do. In particular, this wedding exists since $\widetilde{w_1}$ and $\widetilde{w_2}$ cannot cross again due to $\widetilde{c_1},\widetilde{c_2}$ and $\widetilde{c_3}$ acting as barriers for $\widetilde{s_1}$ and $\widetilde{s_4}$. Since $\tilde{c}$ intersects $\tilde{e}$, it must intersect either $\widetilde{w_1}$ or $\widetilde{w_2}$ and thus $c$ intersects $w$ essentially. This concludes the proof. $\mathrm{⊲}$

Therefore, the family $𝒮\cup {𝒮}_2$, intersects every possible simple non-contractible curve in the surface: it is filling. This claim concludes the proof. $◀$

We encapsulate this last result in the following definition: we say that a system of curves $𝒞$ is $k$-saturating if there exists another system of curves $𝒮$ such that:

• $\mathrm{■}$

  $𝒞\cup 𝒮$ is in minimal position,

• $\mathrm{■}$

  Each curve in $𝒮$ has length at most $k$, and

• $\mathrm{■}$

  The system of curves $𝒮$ is filling.

Therefore, Proposition 7 shows that a face-bipartite $k$-irreducible system of curves is $2k$-saturating. The following lemma shows that one can extract a filling family of size $O(g)$ from any filling family. This is certainly folklore, see for example Chen [14, Theorem 3.15]. We include a proof in the full version [21] for completeness.

We can now combine our tools to obtain a first polynomial upper bound.

By the definition of a $k$-saturating system of curves and thanks to Lemma 12, there exists a filling family $𝒮={(s_i)}_{i\in I}$ of closed curves of length at most $k$ with respect to $𝒞$ and of size at most $3g-1$. In particular, for every $i\in I$, $\mathrm{cr}(s_i,𝒞)⩽k$.

Recall that by the definition of $k$-saturating, the system $𝒞\cup 𝒮$ is in minimal position. We think of $𝒮$ as a $4$-valent graph that is a combinatorial surface. In other words:

• $\mathrm{■}$

  Every curve of $𝒞$ intersect transversely the curves $s_i$, and

• $\mathrm{■}$

  Every intersection vertex of $𝒞$ is inside a face of $𝒮$.

We denote by $F$ the faces of $𝒮$. For such a face $f$, let $p(f)$ denote the perimeter of $f$ i.e. the number of crossings of $𝒞$ with the boundary of $f$. Then, by double counting, ${\displaystyle \sum _{f\in F}}p(f)=2\mathrm{cr}(𝒮,𝒞)⩽2\cdot k\cdot \mathrm{\#}𝒮⩽2(3g-1)k$.

Similarly let $n(f)$ denote the number of vertices of $𝒞$ in the face $f$. Then $\mathrm{cr}(𝒞)={\displaystyle \sum _{f\in F}}n(f)$. As $𝒞$ is in minimal position, the restriction of $𝒞$ to any face $f$ is also in minimal position. This implies that any two curves in $𝒞$ cross at most once in $f$, since otherwise they would form a bigon and thus would not be in minimal position. Thus $n(f)⩽{\displaystyle \frac{p(f)\cdot (p(f)-1)}{2}}$. So

$◀$

Combining Proposition 7 and Theorem 13 provides us with a first bound of $O(k^2{g}^2)$ on the number of vertices in a $k$-irreducible system of curves, and thus on the number of edges in a $k$-irreducible triangulation via the reduction in Section 3. In the next section we add another ingredient to strengthen this bound to $O(k^{2}g)$.

Let $G$ be the intersection graph of $𝒜$: it has one vertex per arc of $𝒜$ and an edge between vertices corresponding to intersecting pair of arcs. By definition, $G$ has $p$ vertices and $n$ edges.

Let $M_G$ be the map graph of $𝒜$ which has one vertex for each face of $𝒜$, including the outer face, and edges between vertices corresponding to faces that share at least one vertex. Let $\mathrm{rad}(M_G)$ be its radius, that is, the minimum radius of a ball that covers $M_G$. Then, by [27, Theorem 5], we have $\mathrm{tw}(G)⩽6\cdot \mathrm{rad}(M_G)+7$, where $\mathrm{tw}(G)$ denotes the tree-width of $G$.

Let $v_{\mathrm{\infty }}$ be the vertex of $M_G$ corresponding to the external face. Then $v_{\mathrm{\infty }}$ is at distance at most $d$ from every face of $𝒜$ in the dual graph of $𝒜$. It follows from the definitions that the distances in the map graph are smaller than the one in the dual graph, so $v_{\mathrm{\infty }}$ is at distance at most $d$ in $M_G$ from every point of $M_G$. Thus $\mathrm{rad}(M_G)⩽d$ and $\mathrm{tw}(G)⩽6d+7$.

Since a graph of tree-width $t$ and $v$ vertices has strictly less than $tv$ edges, $(6d+7)p⩾n$. $◀$

We can now conclude the proof of Theorem 2.

The proof starts like the proof of Theorem 13. By Proposition 7 and Lemma 12, a $k$-irreducible system of curves is $2k$-saturating and thus there is a filling family $𝒮$ of at most $3g-1$ closed curves of length at most $2k$ with respect to $𝒞$. We think of $𝒮$ as a $4$-valent combinatorial surface with a family of faces $F$ and denote by $n(f)$ the number of vertices of $𝒞$ in a face $f$, and by $p(f)$ the perimeter of $f$, i.e., the number of intersections of $𝒞$ and the boundary of $f$.

Assume that there is a face $f$ such that $n(f)>(3k+7)p(f)$. By Lemma 15, $(6d+7)p(f)>(3k+7)p(f)$ and thus $d>k/2$. In this case, there is a point $R$ in $f$ so that any path from $R$ to the boundary of $f$ crosses more than $k/2$ curves of $𝒞$. This point $R$ lies in a face of $𝒞$, and this implies that smoothing one of the vertices on the boundary of that face cannot change the length of any non-contractible closed curve of length $k$, since any such curve going through (two consecutive edges adjacent to) that vertex (as in Claim 9) must be longer than $k$. See Figure 7. Thus $𝒞$ is not a $k$-irreducible system of curves. $\mathrm{⊲}$

We conclude using ${\displaystyle \sum _{f\in F}}n(f)=\mathrm{cr}(𝒞)$ and ${\displaystyle \sum _{f\in F}}p(f)=2\mathrm{cr}(𝒮,𝒞)⩽2(3g-1)2k$, which gives

$◀$