Classification of higher grade ℓ graphs for ^2 × multi-matrix models

We studied in [Ann. Inst. Henri Poincaré D 9, 367-433, (2022)], a complex multi-matrix model with $\mathrm{U}(N)^2 \times \mathrm{O}(D)$ symmetry, and whose double scaling limit where simultaneously the large-$N$ and large-$D$ limits were taken while keeping the ratio $N/\sqrt{D}=M$ finite and fixed. In this double scaling limit, the complete recursive characterization of the Feynman graphs of arbitrary genus for the leading order grade $\ell=0$ was achieved. In this current study, we classify the higher order graphs in $\ell$. More specifically, $\ell=1$ and $\ell=2$ with arbitrary genus, in addition to a specific class of two-particle-irreducible (2PI) graphs for higher $\ell \geqslant 3$ but with genus zero. Furthermore, we demonstrate that counting the 2PI graphs with a single $\mathrm{O}(D)$-loop corresponds to enumerating the alternating knots using the Rolsen's table results, performing a connected sum, or Tait flyping moves on them.

§ INTRODUCTION

Tensor models are derived from the idea that the classical geometry of some manifold could emerge from the statistical sum of random geometries associated with triangulations of this background in attempts to generalize in higher dimensions matrix model results on 2D quantum gravity (QG) <cit.>. They may also be related to a broader hypothesis that gravity is derived from more fundamental (quantum) objects and laws <cit.>.

One of the most compelling findings in this area comes from the special case of matrices. In fact, the Feynman integral of matrix models generates ribbon graphs arranged in a $1/N$ (or genus) expansion, allowing this statistical sum to be effectively controlled using only analytical methods <cit.>. In the large $N$ limit, only planar graphs contribute to leading order. Invariant matrix models undergo a phase transition to a continuum theory of random infinitely refined surfaces when the coupling constant is tuned to some critical value because planar graphs form a summable family. Matrix models, which are related to conformal field theory on fixed geometries, provide a framework for the analytic study of two-dimensional random geometries coupled with conformal matter. Furthermore, because of the fact that their Feynman diagrams are dual to piecewise flat manifolds of dimension two (for matrices) and higher (for tensors), their free energy is the generating function of connected piecewise flat manifolds, which in the continuum limit is anticipated to define a functional integral for Euclidean quantum gravity <cit.>.

The success of matrix models inspired their generalization to random tensor models in higher dimensions, as cited. In the case of tensor models, the crucial $1/N$ expansion tool that leads to understanding and control of the partition function was missing. A method for understanding the partition function of tensor models analytically was abandoned for a while, and as a result, computations in theories implementing a discrete version of QG in higher dimension rely heavily on numerics even today. In fact, tensor models have failed to provide an analytically controlled theory of random geometries. No progress could be made because no generalization of the $1/N$ expansion to tensors has been found for a long time. Tensor models' interest could have been significantly increased if they were given an appropriate notion of $1/N$-expansion. This is exactly what happened after Gurau's flawless discovery of a genuine notion of large $N$-expansion for a specific class of random tensor models <cit.>. This class includes colored tensor models that are associated with triangulations of simplicial pseudo-manifolds in any dimension <cit.>. The colored models' perturbative series supports a $1/N$ expansion indexed by Gurau degree, a positive integer that plays the role of the genus in higher dimensions but is not a topological invariant. Melonic, or leading order graphs, triangulate the $D$-dimensional sphere in any dimension and are a summable family <cit.>.  Tensor models, like their two-dimensional counterparts, go through a phase transition to a theory of continuous infinitely refined random spaces when tuned to criticality. Colored random tensors provide the first analytically accessible theory of higher-dimensional random geometries. They are discovered to go through a phase transition into the so-called branched polymer phase <cit.>. More findings address long-standing issues in statistical mechanics on random lattices and mathematical physics <cit.>.

The leading order (Gurau degree zero) of a $1/N$ expansion of tensor models is indeed well understood; it is dominated by melonic graphs <cit.> and topologically they represent a subclass of spheres. For the higher orders in $1/N$ expansion (i.e., Gurau degree bigger than zero), it is known that indeed, given a Gurau degree, there is a finite number of schemes
and each scheme corresponds to a summable class of graphs.
However, except for the lowest orders (small Gurau degree)
we do not know much about the classification of graphs of arbitrary Gurau degree.

Given a summable class of Feynman graphs, we are interested in their continuum limit.
For the class of diagrams selected by the large-$N$, such a continuum limit is possible, and it leads to two well-defined and ubiquitous continuum probabilistic models: the continuous random tree (so-called branched polymers)
and the Brownian sphere
Typical matrix models lead to the latter, while typical tensor models to the former
but special models can be built with exchanged continuum limits
Finding different limits from these two remains an open problem, of particular relevance to quantum gravity, as neither branched polymers nor the Brownian spheres approach a classical geometry at large distances in higher dimensions than two.
It would therefore be desirable to find other variations of large-$N$ limits selecting different classes of Feynman graphs that could lead to new continuum models, potentially yielding a different limits from the familiar two described above.

A variation of large-$N$ limit was introduced by Ferrari in
and further developed and generalized in
The fundamental variables can be described either as $D$ different $N\times N$ matrices,
(therefore it is named a multi-matrix model),
or as a tensor.
In such a multi-matrix model, there are two parameters to play with owing to the presence of $D$ and $N$ in comparison to the more conventional tensor model governed by only one parameter, Gurau degree coming from having only $N$.
Now with two parameters, different limits can be taken.
In particular, the large-$N$ limit of such models leads to a genus expansion, but one can furthermore perform the large-$D$ limit, thus introducing a new expansion at each fixed genus.
In a typical model, sending both $N$ and $D$ to infinity leads back to the large-$N$ limit of order-$3$ tensors, with melonic dominance (vanishing Gurau degree graphs), and hence to a branched polymer model.
In <cit.>, subclass of higher orders of such double expansion of a multi-matrix model has been studied, namely vanishing grade $\ell=0$ but all genera $g$.
Specifically, they considered a $\mathrm{U}(N)^2\times \oD$ multi-matrix model,
which carries a nice geometric interpretation of its Feynman graphs.
The ribbon structure generated by the propagation of $\mathrm{U}(N)^2$ indices is dual to quadrangulation of orientable surfaces of arbitrary genus.
Then, $\oD$ symmetry decorates these surfaces by
cyclic patterns, called $\oD$-loops.
One can articulate that the statistical properties of the genus are controlled by the large-$N$ limit, while the proliferation of $\oD$-loops – captured by a second integer number
that we call the grade – is directly tied to the large-$D$ limit.
Therefore, one can say that this model exhibits an interplay between topological (genus) and combinatorial ($\oD$-loops) aspects.
By combinatorically grading ($\ell$) the topological property ($g$) or vice versa, we may be able to find summable classes of Feynman graphs of this model.

Speaking of the vanishing genus case, and the fact that the graphs we are studying are $4$-regular, we believe that the enumeration of such graphs is possible by making use of alternating knots. In fact, given a connected planar graph $G$, its medial graph $M(G)$ contains a vertex for each edge of $G$, as well as an edge between two vertices for each face of $G$, with the corresponding edges occurring consecutively. The edges of $M(G)$ are drawn in the corresponding faces, and $M(G)$ is then treated as a planar graph. The medial graph or $4$-regular graph can be associated with an alternating link using checkerboard coloring, where each crossing in the link diagram corresponds to a vertex of the graph <cit.>.

The paper is organized as follows.
In Section <ref>, we briefly review the essential of the $\uN^2 \times \oD$ multi-matrix model on which we extend the analysis done in <cit.> in this present work. In particular, our analysis extends to $\ell > 0$ classification whereas they focused on the classification of $\ell=0$ graphs in <cit.>.
In Section <ref>, we characterize the Feynman graphs generated by the $\uN^2 \times \oD$ multi-matrix model. Using combinatorial moves (Subsection  <ref>), we analyze the properties of Feynman graphs for $\ell=1$, and $\ell=2$ (Subsection <ref>).
Subsection <ref> gives a complete characterization of $\ell=1$ and $\ell=2$ graphs with arbitrary genus $g$ via recursion. We classify planar ($g=0$) $\ell=3$ graphs in Section <ref>. In Section <ref>, we give some classification of subclass of graphs (the 2PI graphs) with $\ell >3$. We make concluding remarks with open questions in Section <ref>. Appendix <ref>, gives some examples on how to recursively construct the 2PI graphs of a given $\ell$ (1 or 2) from lower genus graphs. The construction of the 2PR graphs for $\ell=2$ is given with explicit examples in Appendix <ref>. Finally, Appendix <ref> provides some alternating knots as well as the corresponding 4-regular planar graphs.

§ THE $\UN^2 \TIMES \OD$ MULTI-MATRIX MODEL

We consider an $\oD$-invariant complex matrix model in zero dimension with  $D$ complex matrices $X_\m$ of size $N\times N$ and we may write $(X_\mu)_{ab} = X_{\mu ab}$ where $1\leq \mu\leq D$ and $1\leq a,b\leq N$.
Indeed, one can view such $X$ as order-3 tensor, therefore this model can be viewed as order-3 $\uN^2 \times \oD$-invariant tensor model.

The $\uN^2\times \oD$ multi-matrix model is a model involving a vector of $D$ complex matrices of size $N\times N$, denoted by $(X_\mu)_{\mu=1,\dots,D} =(X_1, \dots,X_D)$ which required to be invariant under unitary actions on the left and on the right of each $X_\mu$,

X_μ→X'_μ= O_μμ' U_(L) X_μ' U_(R)^†  ,
where $O$ is an orthogonal matrix in $\oD$, while $U_{(L)}$ and $U_{(R)}$ are two independent unitary matrices in two distinct copies of the group $\uN$, which we call left and right, respectively.

The free energy of this model is given by

(ł) = log∫[dX]   e^-S[X,X^†]  ,

with a measure $[dX] = \prod_{\mu,a,b} d{\rm Re} (X_\mu)_{ab}\, d{\rm Im}(X_\mu)_{ab}$ and an action $S[X,X^\dagger]$ studied in <cit.> is given by

S[X,X^†] = ND (  [ X^†_X_] - ł/2√(D)   [ X^†_X_X^†_X_] ) .
where the interaction term is known as the tetrahedral interaction and $\lambda$ is the corresponding coupling constant. The coupling constant $\lambda$ has been scaled in such a way that it is kept fixed as $N,D \rightarrow + \infty$. This scaling yields well-defined large $N$ and large $D$ expansions <cit.>, as further detailed below. The perturbative expansion in  $\lambda$ of the free energy $\cF(\lambda)$ enables a graphical description in terms of connected Feynman graphs. These Feynman graphs can be represented in three equivalent ways:

i) as $4$-regular directed orientable maps with the following properties: each vertex has two outgoing and two ingoing half-edges, and additionally, the two outgoing (resp. two ingoing) half-edges appear on opposite sides of the vertex. It should be noted that self-loops/tadpoles and multiple edges are allowed in these maps, and an example is provided in Figure <ref>, left column;

ii) as directed orientable stranded graphs that are $4$-regular, obtained from the above representation by replacing each edge with a triple of parallel strands, two external and one internal, as shown in the top right corner of Figure <ref>.  Since the two $\uN$ symmetry groups' indices are carried by the external strands, they can be distinguished.
When an external strand is on an edge connecting two half-edges, it is referred to as being left (resp. right) depending on which side of the edge it is on.  To the $\oD$ symmetry group, the internal strand is equivalent. According to the tetrahedral interaction's structure (see Figure <ref>, right column), each vertex's contraction pattern for the three different types of strands is determined. It is designed in such a way that a strand of a specific type (left, right, or internal) is always connected to another strand of the same type.  The strands in a Feynman graph are closed into loops.  External strand loops correspond to the faces of the underlying $4$-regular map and form a ribbon graph; we call them L- or R-faces, depending on whether they are made up of left or right strands. The loops formed from internal strands will be referred to as straight faces or $\oD$-loops.

iii) as four-colored graphs obtained in the same manner as tensor models <cit.>.

Notice that the Feynman graphs correspond to graphs embedded on Riemann surfaces and are dual to discretized surfaces; thus, the $\oD$-loops can be thought of as loops drawn on these discretized surfaces.
From the standpoint of tensor models, the Feynman graphs can also be viewed as dual to discretizations of three-dimensional pseudo-manifolds, which are indeed non-orientable in general <cit.>.

Propagator and vertex representations in the map (left) and stranded graph (right). The edge orientations are left implicit in the stranded representation for simplicity (note that fixing the orientation is equivalent to choosing R and L strands).

The free energy in <cit.> has double expansions in $1/N$ and $1/\sqrt{D}$,

(ł) = ∑_g∈ℕ N^2-2g ∑_ℓ∈ℕ D^1+g-ℓ/2 _g,ℓ(ł) ,

where $g\in\mathbb{N}$ is the genus of the corresponding $\uN^2$ ribbon graphs or, equivalently, the genus of the $4$-regular maps, which is also called the genus of the corresponding Feynman graphs. Through Euler's relation, it is defined by:

2-2g = -e+v+f_L+f_R = -v +f  ,
where $e$ denotes the number of edges or propagators, $v$ the number of vertices ($e=2v$ because the maps are $4$-regular), $f_L$ (resp. $f_R$) denotes the number of L-faces (resp. R-faces) and $f=f_L+f_R$. Another parameter associated with Feynman graphs is the quantity $\ell\in\mathbb{N}$.

The parameter $\ell$ is given by:

ℓ/2 = 2 +  v - 1/2f  - φ ,
where $\varphi$ denotes the number of straight faces or $\oD$-loops.

The parameter $\ell$ introduces an extra grading in the standard genus expansion of matrix models, as shown in Eq. (<ref>). As a result, we call it the grade.[The parameter $\ell$ was called index in
whereas this name was used for a different quantity in
To avoid confusion, in <cit.>, a new name, grade, was introduced for it, and we follow here.]

Using Eq. (<ref>), we obtain the following.

The grade $\ell$ of Feynman graph can be expressed by the following relations:

\begin{eqnarray}\label{eq:seven}
\frac{\ell}{2} &=& 1+g+ \frac{1}{2}v-\varphi \,,\cr
\f{\ell}{2} &=& g_L + g_R \,,
\end{eqnarray}

where $g_L$ (resp. $g_R$) is the genus of the ribbon graph obtained by deleting the $L$ (resp. $R$) strands from a Feynman graph in the stranded representation. Since $g_i \in\frac{\mathbb{N}}{2}$ for $i=L,R$ (the corresponding ribbon graphs are not necessarily orientable), $\ell\in\mathbb{N}$ follows.

We make an important remark here that indeed, our model defined by (<ref>) makes direct contact with the literature in tensor models in the following sense.
For $D=N$, we recover the large $N$ structure of  $\mathrm{U}(N)^2 \times \mathrm{O}(N)$
and $\mathrm{O}(N)^3$
tensor models

(ł) = ∑_∈ℕ/2 N^3-  _(ł) ,
where $\omega$ is an important combinatorial quantity called Gurau degree <cit.>.

ω= g+ℓ/2  ,
which is also called the Gurau degree[ It may be called index in the more general context of <cit.>.] <cit.>
appearing in tensor model literature, which governs the large $N$ expansion of tensor models.

We  reorganize (<ref>) as

(ł) = ∑_g∈ℕ (N√(D))^2-2g ∑_ℓ∈ℕ D^2-ℓ/2 _g,ℓ(ł)  .

We keep fixed
as we take $N\to\infty$ and $D\to\infty$. Then,

lim_ N,D→∞
M<∞  1D^2 (ł) = ∑_g≥0 M^2-2g  _g,0(ł) ≡^(0)(M,ł)  .

In other words, by allowing $D\neq N$, but keeping the ratio constant, we obtain a double-scaling limit that selects Feynman graphs with $\ell=0$, but of any genus. Since such graphs are much fewer than all the possible graphs, they lead to a summable series as worked out in <cit.>.

In our present work, we will look at higher $\ell$ graphs corresponding to higher orders in this double scaling limit.

RECURSIVE CHARACTERIZATION OF FEYNMAN GRAPHS WITH $\ELL=1,2$ WITH ARBITRARY $G$

We perform a detailed combinatorial analysis of Feynman graphs with grades $\ell=1$ and $\ell=2$ for arbitrary $g$ in this section,
culminating in a complete characterization of Proposition <ref> and Theorem <ref>.

§.§ Combinatorial structures of Feynman graphs

We introduce definitive combinatorial structures on our $\uN^2 \times \oD$ multi-matrix model.
The majority of the structures listed below were first introduced in tensor model literature <cit.>.

Remark that in this present work, we will work with unrooted Feynman graphs, whereas the preceding work <cit.> exclusively worked with rooted Feynman graphs.

Let us first introduce the cycle graph, a specific Feynman graph that corresponds to an oriented edge; see Figure <ref> for illustration. It is characterized by $v=0$, $f=2$, and $\varphi=1$ by convention and has $g=\ell=\omega=0$ in particular.

The cycle graph on the left and its stranded representation on the right. The black line on the right panel represents the $\mathrm{O}(D)$-loop or straight face, while the green and blue lines represent the L- and R-faces respectively.

§.§.§ Melons and melon-free graphs

i)  An  elementary melonic 2-point subgraph is the subgraph represented on the right side of Figure <ref>, where the two external half-edges or legs are distinct.

ii) A melonic insertion on an edge $e$ of a Feynman graph is the replacement of $e$ by an elementary melonic $2$-point subgraph, respecting the orientation (see Figure <ref>). The reverse operation is called a melonic removal.

iii) A  melonic Feynman graph is a graph which can be reduced to the cycle-graph by successive removals of elementary melonic $2$-point subgraphs.

Insertion of a $2$-point elementary melonic subgraph.

A Feynman graph is said to be melon-free if it lacks any elementary melonic $2$-point subgraph.  The
cycle-graph is the only
Feynman graph with $\omega=g=\ell=0$ that is not a melon.  Because of the following result
<cit.>, we can limit our investigation to melon-free
Feynman graphs.

From <cit.> we can make the following remarks:

$\bullet$ The melonic Feynman graphs are exactly the Feynman graphs of Gurau degree $\omega=0$, that is of genus $g=0$ and of grade $\ell=0$.

$\bullet$ The genus, grade, and Gurau degree are all preserved when a melonic insertion or removal is performed.

$\bullet$ The closed equation

T(λ)=1+λ^2 T(λ)^4  ,
is obeyed by the generating function  $T(\lambda)$ of melonic Feynman graphs.
Remark that indeed $T(\lambda)$ is the generating function for Fuss-Catalan numbers.

A sequence of successive melonic removal can produce any Feynman graph $G$ from a melon-free Feynman graph, known as the core of $G$. The cycle-graph, in particular, is the core of any melonic Feynman graph.

§.§.§ Schemes

A dipole  is defined as a two-edge subgraph  on two vertices with a face of length two. Dipoles are classified into three types (see  Figure <ref>):

* N-dipoles, which contain a length-two straight face;

* inner dipoles or I-dipoles, which contain a length-two inner (I-) face, which can either be L-, or R-face;

* outer dipoles or O-dipoles, which contain a length-two outer (O-) face, which can either be L-, or R-face.

According to Figure <ref>, which shows one pair on the left side of the dipole and the other pair on the right, the four half-edges/external legs incident to a dipole can be canonically divided into two pairs. The composition of dipoles into ladders, which we now define, will benefit from this distinction.

A priori, an $\oD$-loop of length $2$ can be of two forms given by the first two subgraphs in Figure <ref>. The first one is the familiar N-dipole. However, one can observe that the second subgraph is in fact also a N-dipole by rotating a vertex by $180$ degrees as shown in the figure.

$\oD$-loops of length $2$ are contained in N-dipoles.

A N-dipole, two types of I-dipoles,
and  two types of O-dipoles
are shown from left to right.
The upper row shows so-called Feynman graph
representation, while the lower row depicts the associated stranded structures.
An I-dipole (resp. O-dipole) is defined as having faces with a length-two internal (resp. outer) face (which can be L- or R-face). Green (resp. blue) strands are L- (resp. R-) faces.

$\bullet$ A ladder is a sequence of $n\geq2$ dipoles $(d_1, ..., d_n)$ in which two consecutive dipoles $d_i$ and $d_{i+1}$ are connected by two edges that involve two half-edges on the same side of $d_i$ and two half-edges on the same side of $d_{i+1}$.

If a ladder has rungs of different types, it is said to be broken, or a B-ladder;
otherwise, it is unbroken. As a result, there are three types of unbroken ladders: N-, I-, and O-ladders, which contain only rungs of type N, I, and O, respectively.
As a result, if it is an I-ladder (resp. O-), it should only contain one type of dipole, either I- or O-, and not both.

$\bullet$ If a ladder is not included in a larger ladder, it is maximal.

The dipoles in a ladder are referred to as rungs and the edges connecting them are divided into two rails.
to keep track of the external face structure of ladders, we must divide N-ladders into two subfamilies: $\Ne$-ladders with an even number of rungs and $\No$-ladders with an odd number of rungs. This is illustrated in Figure <ref>.

Feynman graphs and ladders which have at least two rungs. Any ladder can be extended into a maximal ladder in a unique way, and two distinct maximal ladders are vertex-disjoint.

The statements are true due to our conventions.

The following replaces maximal ladders with
new type of 4-point vertices that we refer to as ladder-vertices[In the citation <cit.>, they are referred to as chain-vertices.]. There are four different kinds of ladder-vertices; $\Ne$-, $\No$-, I-, O-, and B-vertices. Figure <ref> serves as an illustration.
We simply refer to them as N-vertices when we do not need to distinguish between $\Ne$- and $\No$-vertices.

Maximal ladders and their ladder-vertices. We have represented the parent maximal ladders they represent (left panel) and the structure of their external faces (right panel) for each type of ladder-vertex (center panel).
The external legs on the two sides of each ladder-vertex are fixed by convention. In particular, this might entail `twisting' the two rails at one end of the corresponding B-ladder in the case of a B-vertex.

Assume $G$ is a connected, melon-free Feynman graph. The scheme $S_G$ of $G$ is the graph obtained by replacing any maximal ladder with the ladder-vertex of the corresponding type.

We will heavily rely on schemes, which describe equivalence classes of Feynman graphs defined up to melon and ladder insertions, in the remaining sections of the paper.

More broadly, we will consider the larger family of Feynman graphs with ladder-vertices, which consists of all connected graphs constructed from edges, standard vertices, and ladder-vertices (see Figure <ref>).  A scheme is, by definition, a Feynman graph with ladder-vertices. The converse, however, is not always true.

Feynman graphs with ladder-vertices and schemes are made out of: edges, standard vertices and ladder-vertices.

We renamed the dipoles and ladder-vertices to I-, and O-, from L-, and R- the latter of which were used in <cit.>.
This is because what actually matters for the values of $\ell$ and $g$ is the structure of the dipoles and not necessarily whether internal face of a dipole is L-, or R-.
we need to keep track of orientations of the edges (which carry the same information as whether a face is L- or  R-).
We illustrate our claim above by looking at some examples give in Figure <ref>.
In the left box of Figure <ref>, we show schemes of $\ell=2$, $g=0$, where we may interchange I- and O-ladder-vertices and flip the orientations of edges. This case is a special case where the schemes with I- and O-ladder-vertices happened to be isomorphic if the edge orientation assignment is flipped. Nevertheless, it is still true that if the structure of the schemes are the same (i.e., if the schemes have the same type of a ladder-vertex (I- or O-)), then the values of $\ell$ and $g$ are of course the same.
On the other hand, we show in Figure <ref> demonstrated in the middle and right boxes, that we clearly illustrate what determines the values of $\ell$ and $g$ is the structure of the schemes, namely whether the scheme has I-, or O-ladder-vertices. Even if the edges orientations are flipped (therefore, L-face dipoles become R-face dipoles), the values of $\ell$ and $g$ are the same. However, once the structure of the schemes are different (e.g., I- vs O-), then the schemes are not isomorphic as it is obvious from the fact that they have different values of $\ell$ and $g$.

What matters for the values of $\ell$ and $g$ is the structure of the dipoles (i.e., whether it is I-, or O-) and not necessarily whether internal face of a dipole is L-, or R-.
The middle box shows schemes with $\ell=3$, $g=0$ with I-vertex. In the middle box, the I-vertex in the top scheme has L-rungs, whereas the bottom I-vertex has R-rungs. Nevertheless, both schemes have $\ell=3$ and $g=0$.
Similarly, in the right box, we have O-vertex with R-rungs in the top scheme and on the bottom O-vertex with L-rungs. Both schemes have $\ell=5$ and $g=1$.
In the left box, we show a special case where schemes with different structures (I-, or O-) are isomorphic.

The following result is well known in <cit.>.

Let $G_1$ and $G_2$ be two Feynman graphs that are connected but do not contain melon. If $S_{G_1} = S_{G_2}$, then:
g(G_1) = g(G_2)  ,     ω(G_1) = ω(G_2)     and     ℓ(G_1) = ℓ(G_2) .

A Feynman graph with ladder vertices $G$ can itself be mapped to a unique scheme $S_G$ (obtained by consistent replacement of melon two-point functions by propagators, and ladders by their corresponding ladder-vertices), which allows to define: $g(G):= g(S_G)$, $\omega(G):= \omega(S_G)$ and $\ell(G):= \ell(S_G)$.  In other words, the genus, Gurau degree, and grade of any equivalent class of graphs defined by a scheme are constant.

Finally, distinguishing between two kinds of Feynman graphs with ladder-vertices will be useful. The family of connected Feynman graphs is included in the family of Feynman graphs with ladder-vertices. whether they are two-particle reducible (2PR) or two-particle irreducible (2PI). A Feynman graph with ladder-vertices $G$ is said to be 2PR if it contains an two-edge-cut, which is a pair of edges in $G$ whose removal disconnects $G$. Otherwise, $G$ is 2PI.

It is not hard to prove that a connected melon-free Feynman graph $G$,  $G$ is 2PI if and only if $S_G$ is 2PI.
In general, the 2PR/2PI property is transitive when a maximal ladder is replaced by a ladder-vertex in the class of melon-free Feynman graphs with ladder-vertices.

It is worth noting that we are working on Feynman graphs that allow half-edges to be attached to the vertices. As a result, we assume that the graphs examined throughout this work may have half-edges attached to them. Additionally, we may refer to Feynman graphs as simply graphs.

§.§.§ Combinatorial moves on  Feynman graphs

We now present a set of local operations on Feynman graphs with ladder-vertices and investigate how they affect the genus, grade, and Gurau degree of these graphs.

A dipole or ladder-vertex contraction is defined as the operation of 1) removing the dipole or ladder-vertex and 2) reconnecting the two half-edges on each side of the dipole or ladder-vertex. A dipole or ladder-vertex insertion is the reverse operation. This is shown in Figure <ref>.

Dipole contraction/insertion (left panel) and ladder-vertices (right panel). $ X \in \{{\rm I}, {\rm O}, {\rm N}_{\rm e}, {\rm B}\}$.

It should be noted that the graph may become disconnected if a dipole or a ladder-vertex contracts. Furthermore, the number of connected components can only increase by one. If the contraction of a dipole or a ladder-vertex increases the number of connected components by one, it is said to be separating; otherwise, it is said to be non-separating.

In the topological sense, a separating (resp. non-separating) N-dipole is also separating (resp. non-separating) because the cycle it constitutes separates (resp. fails to separate) the discretized Riemann surface encoded in the Feynman graph into two disconnected regions.

We shall work with connected graphs. A graph in this class is obtained by the contraction of a non-separating dipole or ladder-vertex.

Assume $G$ is a Feynman graph with ladder-vertices and contains a dipole. If this dipole is separating, we denote the two Feynman graphs with ladder-vertices obtained after contracting it as $G_1$ and $G_2$, respectively; if it is not separating, we denote the resulting Feynman graph with ladder-vertices as $G'$. In both cases, we clearly have $v(G_1)+v(G_2)=v(G)-2$ and $v(G')=v(G)-2$. To investigate the effect of the contraction on the genus, grade, and Gurau degree, one must examine how the total number of faces and $\oD$-loops is affected.

Let $G$ be a Feynman graph with ladder-vertices which contains a dipole.

* In case of a separating N-, I-, or O-dipole, we have the following equations:

\begin{eqnarray}
\label{eq:contSep}
&& f(G_1)+f(G_2)=f(G)\,, \quad  \varphi(G_1)+\varphi(G_2)=\varphi(G)\,, \cr
&& g(G_1)+g(G_2)=g(G)\,, \quad \ell(G_1)+\ell(G_2)=\ell(G) \quad \mathrm{and} \quad \omega(G_1)+\omega(G_2)=\omega(G).
\end{eqnarray}

* In case of a non-separating N-dipole (see Figure <ref> for illustration), we have the following equations:

\begin{eqnarray}
\label{eq:contNonSepN}
\cr
&&g(G')=g(G)-1\,, \quad \ell(G')=\ell(G)-2(\sigma+1) \quad \mathrm{and} \quad \omega(G')=\omega(G)-(\sigma+2),
\end{eqnarray}

$\sigma=-1$ (type I, connecting), $\sigma=0$ (type II, rearranging)[We should underline that the case $\sigma =0$ was overlooked in <cit.> and <cit.>, however, does not affect the $\ell=0$ result.], or $\sigma=1$ (type III).

* For non-separating I- or O-dipole (see an illustration in Figure <ref>) then

\begin{eqnarray}
\label{eq:contNonSepLR}
&& f(G')=f(G)-1+\sigma\,,  \cr
\ell(G')=\ell(G)-(\sigma+3)\,,
\mathrm{and} \quad \omega(G')=\omega(G)-(\sigma+2) \,,
\end{eqnarray}

$\sigma=-1$ (connecting), or $\sigma = 1$.

Assume the dipole is a N-, I-, or O-dipole. In the case of a N-dipole, the contraction removes one internal $\oD$-loop and one internal face in the case of I- and O-dipoles. Furthermore, the number of external faces is unaffected in the case of a N-dipole (the external face structure is the same before and after the contraction), and there is one additional external $\oD$-loop created by the dipole's separating nature. It is the number of external $\oD$-loops and O-faces (resp. I-faces) that remain unaffected in the case of an I-dipole (resp. O-dipole) while one additional external I-face (resp. O-face) is created. As a result, we have the first two relationships in (<ref>). Using Eqs. (<ref>), (<ref>) from which we can write $\omega=3+\frac{2}{2}v-f+\varphi$, we thus obtain the remaining results in (<ref>).

Let us now turn to the case of non-separating N-dipole. The contraction eliminates one internal $\oD$-loop while leaving the number of external faces unchanged. Furthermore, there is one more external $\oD$-loop that is either created, deleted, or unaffected. As a result, we obtain the relations in (<ref>).

Assume we have a non-separating I- or O-dipole. The contraction eliminates one internal I- or O-face while maintaining the same number of external $\oD$-loops and I- or O-faces. There is an additional external I- or O-face that is either created or deleted; thus, in both cases the results follow.

Three types of non-separating N-dipoles. The dotted lines represent the paths of $\oD$-faces. For $\ell=2$, the first two types $\sigma = -1$ (connecting) and $\sigma = 0$ (rearranging) are possible; however, for $\ell=0$ and $\ell=1$, only the first type ($\sigma = -1$) is possible. The third case $\sigma = 1$ is irrelevant for our present study, but will be relevant once one wants to consider $\ell \ge 4$ and $g \ge 1$. In the last row, we show some examples of each type of graph (left for type I, middle for type II, right for type III).

Two kinds of non-separating I- or O-dipoles; we call the first one with $\sigma = -1$ it connecting.  The dotted lines represent the paths that I-, or O-face, respectively, for I-, or O-dipoles of non-separating type take. The first connecting type $\sigma = -1$ is possible for $\ell=2$, but not for $\ell=0$ and $\ell=1$.
On the bottom, we show some examples. The three graphs on the left has a connecting I-dipole, and the one on the right has a I-dipole of $\sigma = -1$ type.

The effect of contracting a ladder-vertex in a Feynman graph with ladder-vertices $G$ is now investigated. We continue to denote the two graphs (resp. the graph) obtained after contracting a separating (resp. non-separating) ladder-vertex in $G$ by $G_1$ and $G_2$ (resp. $G'$). As explained in Section <ref>, one way to examine how the genus $g$, grade $\ell$, and Gurau degree $\omega$ change when a ladder-vertex is contracted is to first replace it with a ladder of dipoles of the corresponding type. In the case of a B-vertex, this ladder can be of arbitrary length and structure. The contraction of the ladder-vertex is then easily seen to be the combination of two moves: 1) the contraction of one dipole in the corresponding ladder, whose analysis has been given above; and 2) the removal of up to two melonic $2$-point subgraphs that may have been generated by the first move due to the presence of other dipoles in the initial ladder. The second step requires no further discussion because it preserves the genus, Gurau degree, and grade (see Section <ref>). We obtained the following result, which is similar to the results in <cit.>.

Let $G$ be a Feynman graph with ladder-vertices which contains a dipole. Let us replace the ladder-vertex with a B-, N-, I-, or O-ladder-vertex, as appropriate.

* In case of a separating B-, N-, I- or O-ladder-vertex, we have the following equations:

g(G_1)+g(G_2)=g(G) ,   ℓ(G_1)+ℓ(G_2)=ℓ(G)   and   ω(G_1)+ω(G_2)=ω(G)   ;

* In case of a non-separating N-ladder-vertex,
we have the following equations:

g(G')=g(G)-1 ,   ℓ(G')=ℓ(G)-2(σ+1)   and   ω(G')=ω(G)-(σ+2)   ,
$\sigma=-1$ (type I, connecting), $\sigma=0$ (type II rearranging)[We should underline that the case $\sigma =0$ was overlooked in <cit.> and <cit.>, however, does not affect the $\ell=0$ result.], $\sigma=1$ (type III);

* Non-separating I- or O-ladder-vertex,

g(G')=g(G)-1/2(σ+1) ,   ℓ(G')=ℓ(G)-(σ+3)   and   ω(G')=ω(G)-(σ+2)   ,
with $\sigma=\pm1$;

* Non-separating B-ladder-vertex,

g(G')=g(G)-1 ,   ℓ(G')=ℓ(G)-4   and   ω(G')=ω(G)-3   .

Assume that we have a separating B-, N-, I- or O-vertex. We begin by replacing the ladder-vertex with a B-, N-, I-, or O-ladder, as appropriate. Because the ladder-vertex is separating, the dipoles in the corresponding ladder must also be separating. As a result, we can apply the result of  Eq. (<ref>) to the contraction of a separating dipole. Furthermore, because melonic removals have no effect on the genus, grade, or Gurau degree of a Feynman graph, we obtain the relationships in (<ref>).

In the case of a non-separating N-vertex, we replace the N-vertex with a N-ladder,
made out of non-separating N-dipoles.
Using the result of Eq. (<ref>) and the properties of melonic removal giving therefore the results in (<ref>).

We now turn to the case of Non-separating I- or O-vertex. The same reasoning as in the previous case leads and using Eq. (<ref>) we obtain the results in (<ref>)

Let us now discuss the last case of non-separating B-vertex. We can substitute a B-vertex for a B-ladder of any length and structure, with all of its dipoles being non-separating. Furthermore, because of the structure of a B-ladder, one can check that the contraction of a non-separating N-dipole always yields one additional external $\oD$-loop (case of Eq. (<ref>) with $\sigma=+1$); and the contraction of a non-separating I- or O-dipole leads to one additional external face (case of Eq. (<ref>) with $\sigma=+1$). As a result, in this final case the results in (<ref>) follow.

In the same spirit as <cit.>, we now review another local operation that will be useful in analyzing 2PR Feynman graphs. Assume $G$ is a 2PR Feynman graph with ladder-vertices. The graph $G$ thus contains a two-edge-cut $(e,e')$ and has the structure depicted on the left of Figure <ref>, where $\tilde G_1$ and $\tilde G_2$ are, by definition, two connected $2$-point non-empty subgraphs.

A flip on $(e,e')$ is defined as the operation of cutting the two edges $e$ and $e'$ and reconnecting the four half-edges two by two, as shown on the right side of Figure <ref>. A flip necessarily divides $G$ into two connected components. The reverse operation of a flip is called a two-edge-connection insertion.

Flip operation on a ladder-vertex 2PR Feynman graph.

The effect of a flip operation on the genus, grade, and Gurau degree of the graphs is summarized in the following result:
<cit.> Let $G$ be a Feynman graph with ladder-vertices and suppose that it contains a two-edge-cut $(e,e')$. Then, the flip operation on $(e,e')$ generates two Feynman graphs with ladder-vertices $G_1$ and $G_2$ satisfying

g(G_1)+g(G_2)=g(G) ,   ℓ(G_1)+ℓ(G_2)=ℓ(G)   and   ω(G_1)+ω(G_2)=ω(G)   .

§.§ Properties of melon-free Feynman graphs with $\ell=1$

The connected, melon-free Feynman graphs with $\ell=1$
or $\ell=2$ and their corresponding schemes are what we are interested in characterizing. As made clear in Eq. (<ref>), they always have an odd number of (standard) vertices for $\ell=1$ and an even number of (standard) vertices for $\ell=2$, respectively. Namely, we observe for $\ell = 1$,
φ= g + v+1/2
implying the number of standard vertices should be odd. While  for $\ell = 2$,

φ= g + v/2
implying the number of standard vertices should be even. The following  lemma provides a more detailed characterization.

We can consider partitions of the total number of edges in terms of the lengths $l_i$ of each $\oD$-loop. We have

\begin{align}\label{partition}
e = \sum_{i=1}^{\varphi}l_i.
\end{align}

We sometimes refer to a family of graphs by specifying their configuration in terms of $l_i$, written as a $\varphi$-tuple $(l_1,l_2,\ldots,l_{\varphi})$. For example, in section <ref>, we will study the family of $(4,4,\ldots,4)$ graphs.
We present some lemmas that will be useful several times throughout this work.

Each graph with $l=1$ and $g=0$ has at least one $\oD$-loop with length $2$.

We write a partition of the total number of edges $e$ as in (<ref>). Suppose there are no $\oD$-loops with length $2$. Then because $l_i$ is even, the smallest possible $e$ is obtained when $l_i =4$ for every $i$. We can write

\begin{align}
e \geq 4\varphi = 4\Big( \frac{v+1}{2}\Big) = 2v + 2 > 2v.
\end{align}

Because the graphs we are considering are $4$-regular, we have that $e=2v$.
This gives a contradiction, hence a $\oD$-loop with length $2$ should be present.

In a similar manner, we can achieve the following lemma.

For each graph with $\ell \le 3$ with any $g \ge 1$, it always contains at least one $\oD$-loop of length $2$.

Consider a graph with $\ell\ge 3$ any $g \ge 1$ that does not contain an $\oD$-loop of length two.  Then because $l_i$ is even, the smallest possible $e$ is obtained when every $\oD$-loop has length $4$. From (<ref>), $\varphi = 1+ g + \frac{v}{2} - \frac{\ell}{2}$. We can write for $g \ge 1$,

\begin{align}
e \geq 4\varphi  = 4(1+ g + \frac{v}{2} - \frac{\ell}{2}) = 4 + 4 g  + 2 v -2 \ell
\ge 2 v + 2 (4- \ell)\,.
\end{align}

If $\ell \le 3$, then the above becomes, $e > 2 v$.
Because the graphs we are considering are $4$-regular, we have that $e=2v$.
This gives a contradiction, hence the statement is proven.

Let $G$ be a connected, melon-free
Feynman graph and $S_G$ its scheme of $\ell=1$
$\ell=2$. If $g \ge 1$, then there exists a N-dipole in $G$. In particular, there exists a N-dipole, a N-vertex or a B-vertex
which has at least one N-dipole
in $S_G$.

Let $G$ be a connected, melon-free Feynman graph and $S_G$ its scheme.

$\ell (G) = 1$, any N-dipole in $G$ is separating or connecting; any other dipole is separating.
Furthermore, in $S_G$: any N-dipole or N-vertex is separating or connecting; any other dipole or ladder-vertex is separating.

If  $\ell(G) =2$, any N-dipole in $G$ is separating, connecting (type I), or rearranging (type II), and any I-, or O-dipole is either separating, or connecting. Furthermore, in $S_G$: any N-dipole or N-vertex is separating, connecting (type I) or rearranging (type II), and I-, O-dipole or
I-, or O-vertex is separating or connecting; any other ladder-vertex (namely B-vertex) is separating.

This follows from the variation of the grade under a dipole or a ladder-vertex contraction (see Section <ref>) and from the non-negativity of the grade. Consider a N-dipole in $G$ and suppose it is non-separating. Performing a dipole contraction yields another connected
Feynman graph $G'$ such that, by Eq. (<ref>),

if $\ell(G)=1$ and $\ell\geq0$, it implies $\sigma=-1$.
Hence, the N-dipole is connecting.

Consider now a I- or O-dipole in $G$ and suppose it is non-separating. By Eq. (<ref>), contracting this dipole yields another connected Feynman graph $G'$ such that $\ell(G')\le \ell(G)-2$, which is impossible because $\ell(G) = 1$ and $\ell \geq 0$.

Suppose $\ell(G) =2$ and consider the contraction of a non-separating N-dipole resulting in graph $G'$.  Equation (<ref>) states that
$\ell(G')=\ell(G)-2(\sigma+1)$ with $\sigma=\pm1$ or $\sigma= 0 $.
Since $\ell(G)=2$ and $\ell\geq0$, it implies $\sigma=-1$ or $\sigma = 0$.
the N-dipole is
connecting (type I) or rearranging (type II).

Consider now an I-, or O-dipole in $G$ and suppose it is non-separating. By Eq. (<ref>), contracting this dipole
another connected Feynman graph $G'$ such that $\ell(G')=\ell(G)-(\sigma+3)$, with $\sigma = \pm1$.
Since $\ell(G)=2$ and $\ell\geq0$, it implies $\sigma=-1$ and consequently the dipole is connecting.

The same reasoning applies for any dipole or ladder-vertex in $S_G$ using a dipole or a ladder-vertex contraction and Eqs. (<ref>)-(<ref>).

Unless otherwise stated, we assume that the Feynman graphs are always connected in the following. With the  Corollary <ref>,
Lemma <ref>,
Lemma  <ref>, and Lemma <ref>,
and not we can clearly manipulate the connected, melon-free Feynman graphs with $\ell=1$ and their schemes by successive insertions or contractions of: 1) connecting N-dipoles or N-vertices; and 2) separating dipoles or ladder-vertices.
In the same way, we can also manipulate the connected, melon-free Feynman graphs $\ell=2$ and their schemes by successive insertions or contractions of:
1) connecting (type I) or rearranging (type II) N-dipoles or N-vertices ; 2) separating dipoles or ladder-vertices; and 3) connecting ($\sigma = -1$) I-, or O-dipoles, or I-, or O-vertices.

To lay the groundwork for this construction, it is useful to list the situations in which the contraction of a dipole or a ladder in a $\ell=1$
or $\ell = 2$ melon-free Feynman graph generates a melonic $2$-point subgraph. Assume that $G$ is such a graph and that it contains a dipole or ladder $X$ or $\widetilde X$ (these notations become clearer in the following with reference to Figure <ref>).

For $\ell=1$, if we assume that $X$ or $\widetilde X$ is non-separating, it is necessarily a connecting N-dipole or N-ladder by Lemma <ref>.

For $\ell=2$,
if we assume that $X$ or $\widetilde X$ is non-separating, it is necessarily either

* a connecting ($\sigma = -1$ type I) N-dipole or N-ladder,

* a rearranging ($\sigma = 0$ type II) N-dipole or N-ladder, or

* a connecting ($\sigma = -1$) I-, or O-dipole or I-, or O-ladder,

by Lemma <ref>.

$X$ is a connecting N, rearranging N, connecting I, connecting
O, or separating.
For separating, $X \in  \{$N-dipole, $\No$, $\Ne$, I-dipole, O-dipole, I, O, B$\}$  in $\ell=1$ and $\ell=2$ graphs. For connecting,  $X \in  \{$N-dipole$, \,\No, \,\Ne\}$ in $\ell =1$ graphs,
$X \in  \{$N-dipole,   I-dipole,   O-dipole, $\No$,  $\Ne$, I, O$\}$
in $\ell =2$ graphs.

$X$ is a connecting N.
$X \in  \{$N-dipole,  $\No$$\}$ (note that  $X \ne \Ne$)
in $\ell =1, \,2$ graphs.
On the other hand, in a subgraph with a slightly different structure,
$\widetilde X$ is a rearranging N, a connecting
I, or a connecting
O, i.e.,
$\widetilde X \in  \{\Ne,\, $I-dipole, O-dipole, I, O$ \}$ possible only in $\ell =2$ graphs.
Shown are only one orientation assignment on edges, and one needs to consider the other assignment as well.

$X$ is a connecting N, a connecting
I, or a connecting
$X = \Ne$.
($ X \notin \{$N$, \,\No\}$) in $\ell = 1$ graphs,
$X \in  \{\Ne, \, $I-dipole, O-dipole, I, O$\}$ in $\ell =2$ graphs.
On the other hand, in a subgraph with a slightly different structure,
$\widetilde X$ is a rearranging N, and $\widetilde X \in  \{$N$, \,\No\}$  possible only
in $\ell =2$ graphs.
Shown are only one orientation assignment on edges, and one needs to consider the other assignment as well.

Configurations in which the contraction of a dipole or ladder $X$ or $\widetilde X$
in a
$\ell=1$ or $\ell=2$ melon-free Feynman graph, assumed to be connecting (i.e., any $\sigma = -1$) N,
I, or O, rearranging N,  or separating, generates a melonic $2$-point subgraph (where $Y$ is itself a dipole or a ladder).

When $X$ or $\widetilde X$ is contracted in a Feynman graph $G$ with $\ell=1$
$\ell=2$, a new Feynman graph $G'$ with $\ell=1$
or $\ell=2$ is created. This new graph is not melon-free in the following three situations:

* As shown in Figure <ref>, $X$ is connected on one side to another dipole or ladder $Y$ (of any type). For $\ell=1$, $X$ can be a N-dipole, a N$\mathrm{_o}$-, or a N$\mathrm{_e}$-ladder. For $\ell=2$, $X$ can be a N-dipole, a N$\mathrm{_o}$-, or a N$\mathrm{_e}$-ladder, or a I-, or O-dipole, or a  I-, or O-ladder;

* $X$ or $\widetilde X$
is inserted in between two edges of an elementary $2$-point melon, as illustrated in Figure <ref>. Note that the choice of pair of edges on which $X$ or $\widetilde X$
is inserted, and therefore their orientation, is fixed by the requirement that $X$ is connecting or $\widetilde X$ is rearranging N or connecting  I-, or O-ladder.
As a result, $X$ must be a N-dipole or a N$\mathrm{_o}$-ladder, and $\widetilde X$ must be a N$\mathrm{_e}$-ladder, I-, or O-dipole, or I-, or O-ladder in $\ell=2$ graphs only;

* $X$ or $\widetilde X$
is forming a $2$-point subgraph on one side of a dipole or ladder $Y$ (of arbitrary type), as illustrated in Figure <ref>. Note that the orientations of the edges
are again fixed by the requirement that $X$ is connecting
N or $\widetilde X$ is rearranging N.
As a result, $X$ must be a N$\mathrm{_e}$-ladder in either $\ell=0\,,1\,,2$ graphs,  a
I-, or O-dipole, or a   I-, or O-ladder
and $\widetilde X$ must be a N-dipole or a N$\mathrm{_o}$-ladder only in $\ell=2$ graphs.

If we assume instead that $X$ or $\widetilde X$ is separating, it can be of any type by Lemma <ref>, and its contraction yields two Feynman graphs $G_1$ and $G_2$, such that $\ell(G_1) + \ell(G_2) = \ell(G)$.

We now investigate the structure of melon-free Feynman graphs of any genus with $\ell = 1$ and $\ell=2$.

The upcoming Theorem <ref> will provide all the planar $g=0$, $\ell = 1$  and $\ell=2$ melon-free Feynman graphs by specifying their schemes.

Later on, in Theorem <ref>, we will provide all the $\ell = 1$ melon-free Feynman graphs of $g=1$ by specifying their schemes, and all the 2PI $\ell=2$ melon-free Feynman graphs of $g=1$ by specifying their 2PI schemes.

Finally, Theorem <ref> offers inductive way of recursively constructing all the $\ell=1$ and $\ell=2$ Feynman graphs of any genus.

To begin, let us first recall from <cit.> that there is one  scheme of genus zero (given in Figure <ref>) and one scheme of genus one (given in Figure <ref> with $\ell=0$).

There is only one scheme of $\ell=0$ and $g=0$, the cycle graph.
The left is a colored graph representation, and the right is the stranded notation. Green is L-strand and in blue, we show R-strand.

There is only one $\ell=0$, $g=1$ scheme, $S_1$, including the opposite orientation assignment on the edges.

By plugging in $\ell=2$ in equation (<ref>), we obtain the following relation

\begin{align}
\varphi = g + \frac{v}{2}.
\end{align}

This relation implies that the number of vertices should be even.

For each graph with $\ell=2$, $g=0$,
it either contains at least one $\oD$-loop of length $2$ or every $\oD$-loop is of length $4$.

Consider a planar graph with $\ell=2$ that does not contain an $\oD$-loop of length two and not every $\oD$-loop has length $4$.  Then because $l_i$ is even, the smallest possible $e$ is obtained when every $\oD$-loop but one has length $4$, and the remaining one has length $6$. We can write

\begin{align}
e \geq 4(\varphi-1) + 6 = 4(
\frac{v}{2}-1) + 6 =
2v + 2 > 2v.
\end{align}

Because the graphs we are considering are $4$-regular, we have that $e=2v$.
This gives a contradiction, hence the statement is proved.

We now investigate the number of schemes based on the grade and the genus of the graph we are considering. Before doing so, the following definition gives a direct way to determine whether two schemes are isomorphic or not.

Two schemes $S_1$ and $S_2$ should be isomorphic if there is an isomorphism of the underling graphs that also preserves the faces types and orientations.
In other words, if they have faces of same  length  connected in all the same ways in such a way that if $f$ is a R-face (resp, L- or $\oD$-face) in $S_1$, its correspondence in $S_2$ is also a R-face (resp, L- or $\oD$-face) with the same orientation of $f$.

§.§ Complete characterization of $\ell=1$ and $\ell=2$ with arbitrary $g$

This subsection recursively enumerates  the Feynman graphs with grades $\ell =1, 2$ and arbitrary genus.
The procedure begins with graphs with genus $g=0$,  giving the exact numbers of corresponding schemes  by classifying them as 2PI or 2PR graphs, for $\ell=1, 2$.
For $g=1$, the same is achieved for $\ell=1$, but only for 2PI in the case of $\ell=2$.
These findings were immediately recursively extended to arbitrary genus for $\ell=1, 2$. We should note that the exact numbers of such schemes are not specified for $g >1$, but we provide an algorithm that allows us to fully recover all of them. Furthermore, we should emphasize that we work under the isomorphism condition given in Definition <ref>.

Including the orientations of edges,
there are two schemes of $\ell=1$ and $g=0$ (Figure <ref>). They are the only schemes of $\ell=1$ and $g=0$ and they are 2PI and called the infinity graph.
There are three 2PI schemes (Figure <ref>) and 27 2PR schemes of $\ell=2$ and $g=0$ (Figure <ref>).

All $\ell=1$, $g=0$ schemes.
There are two schemes of $\ell=1$ and $g=0$ in total.
We call this type the infinity graph.

All $\ell=2$, $g=0$ 2PI schemes.
There are three 2PI schemes of $\ell=2$ and $g=0$ in total. Let us call the leftmost type $S_{1}^{2,0}$, the middle and the right type $S_2^{2,0}$.

All $\ell=2$, $g=0$ 2PR schemes.
There are 27 2PR schemes of $\ell=2$ and $g=0$ in total.
Let us call this type (all 27 of them) $S_3^{2,0}$.
$Y \in \{ $I-dipole$, $O-dipole$, {\rm I}, {\rm O}, {\rm N}_{\rm e}, {\rm B}\}$ and $\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.

Let us ignore the orientations of the edges at the moment. We will recover at the end of the proof.
Consider a  graph
with  $\ell=1$, $g=0$. Because of
Lemma <ref>
there is an $\oD$-loop of length $2$ present. If the graph has one vertex, there is only one possibility. It is the cycle graph with one tadpole added, also referred to as the infinity graph, depicted in Figure <ref>.

The infinity graph.

If it has more vertices, then the $\oD$-loop of length two is contained in a N-dipole and the graph will be of the form as the graph on the left hand side of Figure <ref>.
Removing the $\oD$-loop of length 2, as depicted in Figure <ref>,  does not change $\ell$ or $g$. Therefore, we obtain again a planar ($g=0$) graph with $\ell=1$. Consequently, the resulting graph contains an $\oD$-loop of length $2$. We can again remove from the resulting graph the $\oD$-loop of length 2 without changing $\ell$ or $g$. By continuing this procedure of removing an $\oD$-loop with length 2 and keeping $\ell$ and $g$ invariant, we end up with a planar graph with $\ell=1$ and only one vertex.

Removal of an $\oD$-loop of length $2$. Grey discs represent any subgraphs.

By reversing this reasoning, one can conclude that a graph with $\ell=1$, $g=0$ can be constructed from the infinity graph by adding $\oD$-loops of length $2$ giving the graph in Figure <ref>.
In this case, these $\oD$-loops of length $2$ are melons. Therefore, in schemes, we just proved that the infinity graph shown in Figure <ref> is the only $\ell=1$, $g=0$ scheme[In <cit.>, they have proven also that the infinity graph is the only $\ell=1$ $g=0$ scheme.].
If we recover the edge orientation assignment in the infinity graph, we obtain two possibilities for the infinity graph which are depicted in Figure <ref>.

Consider a planar graph with $\ell=2$. If an $\oD$-loop of length two exists, we can copy part of the reasoning from the case for $\ell=1$ and remove $\oD$-loops of length two iteratively while keeping $\ell$ and $g$ invariant. The resulting graph contains no $\oD$-loops of length 2 and thus should only contain  $\oD$-loops of length 4, as explained in
Lemma <ref>.
By reversing this argument, we can conclude that every graph is built from  $(4,4, \ldots, 4)$ graphs by sequentially adding  $\oD$-loops of length 2. Unlike in the case of $\ell=1$, we will see that these $\oD$-loops are not always melons.

In order to discuss the possible configurations of $(4,4,\ldots,4)$ graphs, we first consider the possible configurations of a single  $\oD$-loop of length $4$ appearing in a planar graph.
Suppose the  $\oD$-loop of length four contains two vertices. Then,
ignoring orientations of the edges for the moment,
we have only two possibilities, depicted in  Figure <ref>. They can be constructed from the cycle graph by adding two tadpoles.

Simplest planar graphs with $\ell=2$ with two vertices.

Secondly, suppose the $\oD$-loop contains three vertices. Then we can distinguish two cases given as the first two subgraphs in Figure <ref>. They can be thought as the cycle graph with one tadpole added.
Finally, suppose the $\oD$-loop contains four vertices. Then the only possible $\oD$-loop one can form is the subgraph drawn on the right hand side in Figure <ref>. Note that these $\oD$-loops are only subgraphs of a general graph, hence we let the vertices with their respective free half-edges drawn.

Building blocks of $(4,4,\ldots,4)$ graphs.

The $\oD$-loops of length $4$ just described are the building blocks from which one constructs a general $(4,4,\ldots,4)$ graph. We distinguish two cases:

If the graph does not contain a tadpole, it only contains $\oD$-loops of length $4$ as the one on the right of Figure <ref>. If an $\oD$-loop contains two non-adjacent vertices of another $\oD$-loop, there is only one possibility. The graph is depicted on the left side of Figure <ref>. The only other possibility is by linking the $\oD$-loops together to form a closed chain. It can be easily redrawn with the use of an I-ladder-vertex on the right side of Figure <ref>.

Graphs with $\ell=2$ and no tadpoles.

We now describe how any $(4,4,\ldots,4)$ graph with tadpoles can be constructed. The graph contains a tadpole, hence it contains an $\oD$-loop as either the left or middle subgraph in Figure <ref>. We now have two vertices with each two free half-edges. One can add to this $\oD$-loop another $\oD$-loop of the same kind, i.e. containing a tadpole. Then there are no free half-edges left and the procedure is finished. One can also add the $\oD$-loop of length four on the right side of Figure <ref>. Then there are still free half-edges and the procedure continues. For the next $\oD$-loop to be added and the ones afterwards, we have two options. We either add it to the “inner" edge or the “outer" edge of the previous $\oD$-loop. This choice determines whether the previous two vertices will be part of an I- or O-dipole. We continue the procedure by adding an $\oD$-loop with or without tadpole. The procedure ends by adding an $\oD$-loop with tadpole as discussed before. We end up with a ladder containing I- and/or O-dipoles, with a tadpole on either end.
An example of this procedure is displayed in Figure <ref>, where first two $\oD$-loops without tadpoles are added,  then subsequently end the procedure by adding an $\oD$-loop with tadpole. In this Figure <ref>, it is also shown how the resulting graph can be expressed in terms of dipoles.

Example of construction of $(4,4,\ldots,4)$-graph with tadpoles.

One can therefore construct general planar graphs with $\ell=2$ from the $(4,4,\ldots,4)$ graphs by adding $\oD$-loops of length $2$ that do not change the genus. In the case where there are no tadpoles present, such $\oD$-loops will be melons. In the case where tadpoles are present adding such non-melonic $\oD$-loops,
amounts to adding N-dipoles to the, possibly empty, ladder. All possible schemes of graphs with $\ell=2$, $g=0$ are given in Figure <ref>, after recovering the orientation assignment on edges.

By plugging in $\ell=1$, $g=1$ in equation (<ref>), we obtain the following relation

\begin{align}
\varphi = \frac{v+3}{2}.
\end{align}

This relation implies that the number of vertices should be odd.

Including the orientations of edges, for  $\ell=1$ and $g=1$, there are four 2PI schemes as given in Figure <ref> and 54 2PR schemes  as given in Figure <ref>. There are 48 2PI schemes of $\ell=2$ and $g=1$ as given in Figure <ref> in addition to more 2PR schemes with $\ell=2$ and $g=1$.

All $\ell=1$, $g=1$ 2PI schemes.
There are four schemes of 2PI $\ell=1$ and $g=1$ in total.
$\widetilde {\rm N}_{\rm o}\in\{ $N-dipole$, {\rm N}_{\rm o}\}$.

All $\ell=1$, $g=1$ 2PR schemes.
There are 54 schemes of $\ell=1$ and $g=1$ in total.
${\rm Y} \in \{ $I-dipole$, \, $O-dipole$, \,{\rm I}, {\rm O}, {\rm N}_{\rm e}, {\rm B}\}$. $\widetilde {\rm N}_{\rm o}\in\{ $N-dipole$, {\rm N}_{\rm o}\}$.

All $\ell=2$, $g=1$ 2PI schemes.
There are 48 2PI schemes of $\ell=2$ and $g=1$ in total.
$\widetilde {\rm I} \in \{$I-dipole$, \, $I$\}$, $\widetilde {\rm N}_{\rm o} \in \{$N-dipole$, {\rm N}_{\rm o}\}$.

Let us first take   $\ell = 1$, and consider melon-free Feynman graph $G$ of $\ell=1$ genus one and $S_G$ its scheme.

($\boldsymbol{\ell=1}$, 2PI.)
We begin by assuming that $G$ is 2PI. According to
Corollary <ref>, there must be a connecting (type I) N-dipole in $G$. Because of Lemma <ref>, this N-dipole must be connecting (type I)
(a separating one would violate the 2PI condition).
Furthermore, the maximal extension of this N-dipole in $G$ is either the N-dipole itself or a maximal N-ladder (a B-ladder is necessarily separating by Lemma <ref>), which corresponds to a N-dipole or a N-vertex in $S_G$. The contraction of the maximal extension of this connecting N-dipole with $\Delta \ell = 0$ and $\Delta g = -1$ yields a $\ell=1$ Feynman graph $G'$ of genus zero using  Eq. (<ref>) or (<ref>) with $\sigma=-1$ (by the connecting property).

Now, if $G'$ is not melon-free, we must be in one of the configurations shown in Figures <ref>, <ref>, <ref>. However, the configuration <ref> is excluded by maximality of $X$, while both configurations <ref> and <ref> yield 2PR graphs $G$.
Therefore, $G'$ must be melon-free.

Let us analyze further $\ell=1$ and 2PI graphs $G$ keeping in mind that $G'$ must be melon-free.
If $G'$ is melon-free, it must be the infinity graph which can be either clockwise or counter-clockwise; and the orientation of the edges imposes that the contraction involved  a N$_\mathrm{o}$-ladder. As a result, $S_G$ can be one of the graphs in Figure <ref>.

The schematic instruction on how to obtain the only 2PI $\ell=1$, $g=1$ schemes given in Figure <ref>, starting with $\ell=1$ $g=0$ schemes $G'$ on the left. One cuts the edges where scissors are placed, and insert a N-dipole, or a N-ladder-vertex accordingly. The red dotted lines indicate the paths of  $\oD$-strands. $\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.

($\boldsymbol{\ell=1}$, 2PR.)
We will now assume that $G$ is 2PR.
We distinguish two cases.

In the first case, $G$ contains a separating dipole. We call $X$ its maximal extension and consider its contraction. We call the two resulting graphs $G_1$ and $G_2$.

In the second case, $G$ does not contain a separating dipole. It still contains a two-edge-cut because it is 2PR. We perform the flip operation as described in Lemma <ref> and call the resulting graphs $G_1$ and $G_2$.

In both cases the following equations hold , $\ell(G_1) + \ell(G_2) = \ell(G)$ and $g(G_1) + g(G_2) = g(G)$, as discussed in Propositions <ref> and <ref> in the first case and in Lemma <ref> in the second case. Since $g(G) =1$, we can assume without loss of generality that  $g(G_1)=0$ and $g(G_2) = 1$.

A priori, there are two options:

$g(G_1) = 0$, $\ell(G_1) = 0$ and $g(G_2) = 1$, $\ell(G_2) = 1$. Therefore, $G_1$ is the cycle graph,
possibly decorated with melons.
Since $G$ is melon-free, it is easy to see that $G_1$ should be melon-free as well because of the maximality of $X$ in the first case and because of the non-existence of a separating dipole in the second case. Thus $G_1$ is the melon-free cycle graph. This implies that $G$ is not melon-free in the first case, while in the second case this configuration (where $\tilde G_1 = \emptyset$ in Figure <ref>) is not permitted by the definition of a two-edge-cut. In conclusion, option (a) cannot occur.

$g(G_1) = 0$, $\ell(G_1) = 1$ and $g(G_2) = 1$, $\ell(G_2) = 0$. Thus, $G_1$ is the infinity graph of either clockwise or counterclockwise,
possibly decorated with melons,
and there is also only one possible $G_2$ which is $S_1$ (given in Figure <ref>),
possibly decorated with melons.

Therefore, in the end, we  omit case (a) and we only have one possibility, which is (b) above. Let us examine the case (b) further below.

Suppose $G_1$ or $G_2$ contains a melonic subgraph.

* In the first case, this would violate either the maximality of $X$
(see Figure <ref>)
or the assumption that $G$ is melon-free.

* In the second case, this would violate either the assumption that $G$ does not contain a separating dipole or the assumption that $G$ is melon-free.

Therefore, we conclude that $G_1$ nor $G_2$ cannot contain a melonic subgraph.

Then, the only possibilities are given by Figure <ref> below, ignoring the edge orientation assignment at the moment.
In Figure <ref>
the edge orientation assignments are distinguished.

$\ell=1$, $g=1$ 2PR schemes of $G$ (on the right), which are generated by inserting a separating dipole or separating ladder into $G_1$ (infinity graphs given in Fig. <ref>) and $G_2 = S_1$ given in Fig. <ref>.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$,\, {\rm N}_{\rm o}\}$, $X \in \{$N-dipole$, \, $I-dipole$,\, $O-dipole$, \,{\rm N}_{\rm e}, {\rm N}_{\rm o}, {\rm I}, {\rm O}, {\rm B}\}$.

This concludes that in the end,  we have two types of 2PR graphs for $\ell=1$ and $g=1$ shown in Figure <ref>, which translate to 54 2PR schemes in Figure <ref>
by recovering the edge orientation assignment,  in addition to the only 2PI four schemes shown in Figure <ref>.

Next, let us consider $\ell=2$, and
let $G$ be a
melon-free Feynman graph of $\ell=2$ genus one and $S_G$ its scheme.

($\boldsymbol{\ell=2}$, 2PI.)
We first assume that $G$ is 2PI.
By Lemma <ref>, there necessarily exists a non-separating (either connecting (type I, $\sigma = -1$) or rearranging (type II, $\sigma = 0$)) N-dipole
in $G$ (a separating one would break the 2PI condition).
Furthermore, the maximal extension of this
N-dipole in $G$ is either the
N-dipole itself or a maximal N-ladder respectively (a B-ladder is necessarily separating by Lemma <ref>), which translates into a N-dipole or a
N-vertex in $S_G$, respectively.
Using Eq. (<ref>) or (<ref>),

the contraction of the maximal extension of this connecting ($\sigma=-1$) N-dipole of type I with $\Delta \ell = 0$ and $\Delta g = -1$ yields a $\ell=2$ Feynman graph $G'$ of genus zero,

whereas the contraction of the maximal extension of the rearranging ($\sigma=0$) N-dipole of type II with $\Delta \ell = -2$ and $\Delta g = -1$ yields a $\ell=0$ Feynman graph $G'$ of genus zero.

For both (1) and (2) above, if $G'$ is not melon-free,
we must be in one of the configurations shown in Figures <ref>, <ref>,
However, the configuration <ref>
is excluded by maximality of $X$, while
yield  2PR $G$.
Therefore, $G'$ must be melon-free.

Now, let us further examine the above cases (1) and (2) separately keeping in mind that $G'$ is melon-free.

If $G'$ (can be either 2PI or 2PR a priori) is melon-free, it must be either $S^{2,0}_1$, $S^{2,0}_2$, or $S^{2,0}_3$ given in Figures <ref> and <ref>.
We list $G$s in Figures <ref>, <ref>, and <ref> below, which are generated by inserting a connecting N into respectively $S^{2,0}_1$, $S^{2,0}_2$, and $S^{2,0}_3$.

The 2PI schemes obtained from $S_1^{2,0}$ (2PI) given in Figure <ref> by inserting a connecting N.
See Figure <ref> in Appendix for how to insert a connecting N in order to obtain these schemes. $\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.

The 2PI schemes obtained from $S_2^{2,0}$ (2PI) given in Figure <ref>  by inserting a connecting N.
See Figure <ref> in Appendix for how to insert a connecting N in order to obtain these schemes. $\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$,\, {\rm N}_{\rm o}\}$ and $\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$.

The 2PI schemes obtained from $S_3^{2,0}$ (2PR) given in Figure <ref> by inserting a connecting N.
See Figure <ref> in Appendix for how to insert a connecting N in order to obtain these schemes.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$,\, {\rm N}_{\rm o}\}$.

If $G'$ is melon-free, it must be the cycle graph;  As a result, $S_G$ is the graph below (corresponding to two schemes).

The 2PI schemes obtained from the cycle graph by inserting a rearranging N.
See Figure <ref> in Appendix for how to insert a rearranging N in order to obtain these schemes.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, \,{\rm N}_{\rm o}\}$.

($\boldsymbol{\ell=2}$, 2PR.)
We now assume that $G$ is 2PR.

We distinguish two cases.

In the first case, $G$ contains a separating dipole. We call $X$ its maximal extension and consider its contraction. We call the two resulting graphs $G_1$ and $G_2$.

In the second case, $G$ does not contain a separating dipole. It still contains a two-edge-cut because it is 2PR. We perform the flip operation as described in Lemma <ref> and call the resulting graphs $G_1$ and $G_2$.

In both cases the following equations hold , $\ell(G_1) + \ell(G_2) = \ell(G)$ and $g(G_1) + g(G_2) = g(G)$, as discussed in Propositions <ref> and <ref> in the first case and in Lemma <ref> in the second case. Since $g(G) =1$, we can assume without loss of generality that  $g(G_1)=0$ and $g(G_2) = 1$.

A priori, there are three possibilities:

$g(G_1) = 0$, $\ell(G_1) = 0$ and $g(G_2) = 2$, $\ell(G_2) = 2$. Hence, $G_1$ is the cycle graph,
possibly decorated with melons.
Since $G$ is melon-free, it is easy to see that $G_1$ should be melon-free as well because of the maximality of $X$ in the first case and because of the non-existence of a separating dipole in the second case. Thus $G_1$ is the melon-free cycle graph. This implies that $G$ is not melon-free in the first case, while in the second case this configuration (where $\tilde G_1 = \emptyset$ in Figure <ref>) is not permitted by the definition of a two-edge-cut. In conclusion, option (a) cannot occur.

$g(G_1) = 0$, $\ell(G_1) = 2$ and $g(G_2) = 1$, $\ell(G_2) = 0$. Therefore, $G_1$ is one of corresponding graphs from
Figures <ref> and <ref>. The graph
$G_2$ is $S_1$ in Figure <ref>,
possibly decorated with melons.

$g(G_1) = 0$, $\ell(G_1) = 1$ and $g(G_2) = 1$, $\ell(G_2) = 1$. Thus, $G_1$ is the infinity graph,
possibly decorated with melons,
and $G_2$ is either corresponding 2PI graphs given in Figure <ref>, or corresponding 2PR graphs given in Figure <ref>.

Therefore, a posteriori, (a) must be omitted, and we only have two possibilities (b) and (c) of above.
In both of these cases (b) and (c), let us analyze the situation further.

Suppose $G_1$ or $G_2$ contains a melonic subgraph.

* In the first case, this would violate either the maximality of $X$
(see Figure <ref>)
or the assumption that $G$ is melon-free.

* In the second case, this would violate either the assumption that $G$ does not contain a separating dipole or the assumption that $G$ is melon-free.

Therefore, we conclude that $G_1$ nor $G_2$ cannot contain a melonic subgraph.
Then, we show specific examples below of 2PR $\ell=2$ graphs.
For (b), Figure <ref> shows an example, and more examples can be found in Figure <ref> in Appendix <ref>.
For (c), Figure <ref> illustrates an example, and another example can be found in Figure <ref> in Appendix <ref>.

2PR schemes obtained from combining a $\ell=2$ and $g = 0$  graph $G_1$ with a $\ell=0$ and $g=1$ graph $G_2$ via separating dipole or a ladder-vertex
or a two-edge-connection.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$,\, {\rm N}_{\rm o}\}$.
See more in Figure <ref>.

2PR schemes obtained from combining a $\ell=1$ and $g = 0$  infinity graph $G_1$ with a $\ell=1$ and $g=1$ graph $G_2$ via separating dipole or a ladder-vertex.  $ X\in\{$N-dipole$, \,$I-dipole$, \,$O-dipole$,\, {\rm N}_{\rm e}, {\rm N}_{\rm o}, {\rm I}, {\rm O}, {\rm B}\}$.
See more in Figure <ref>.

This concludes that in the end, we show some  2PR graphs for $\ell=2$ and $g=1$ in Figures <ref> and <ref>,  in addition to the only 2PI ones (48 of them) shown in Figure <ref>.

From the families of  $\ell = 1$ and $\ell=2$ melon-free Feynman graphs of genus $g' < g$, the following theorem provides a method for constructing all of the $\ell=1$ and $\ell=2$ melon-free Feynman graphs of any genus $g$.

Let $G$ be a connected and melon-free Feynman graph, such that  $\ell(G) = 1$ and $g(G) = g \geq 2$.

($\boldsymbol{\ell=1}$, 2PI.)
Suppose first that $G$ is 2PI.
Then it can be obtained by insertion of a connecting N-dipole or N-ladder into a: $\ell=1$, connected and melon-free Feynman graph of genus $g-1$.

($\boldsymbol{\ell=1}$, 2PR.)
Suppose instead that $G$ is 2PR.
Then, $G$ can be obtained by insertion of a separating dipole, a separating ladder, or a two-edge-connection in between:  connected and melon-free Feynman graphs $G_1$ and $G_2$ with
$\ell(G_1) = 1$ and $\ell (G_2) = 0$, such that  $0   \le g(G_1)  < g$, $0 <  g(G_2) \le  g$
and $g(G_1) + g(G_2) = g$.

Let us now suppose $G$ be a connected and melon-free Feynman graph, such that $\ell(G) = 2$ and $g(G) = g \geq 2$.

($\boldsymbol{\ell=2}$, 2PI.)
Suppose first that $G$ is 2PI. Then it can be obtained by insertion of either

* a connecting N-dipole or N-ladder into a: $\ell=2$, connected and melon-free Feynman graph of genus $g-1$,

* a rearranging N-dipole or N-ladder into a: $\ell=0$, connected
and melon-free
Feynman graph of genus $g-1$.

($\boldsymbol{\ell=2}$, 2PR.)
Suppose instead that $G$ is 2PR.
Then one of these two conditions holds:

* $G$ can be obtained by insertion of a separating dipole, a separating ladder, or a two-edge-connection in-between:  connected and melon-free Feynman graphs $G_1$ and $G_2$ with $\ell(G_1) = 2$ and $\ell (G_2) = 0$, such that   $0 \le g(G_1) \le g-1$, $0  < g(G_2) \le g$, and $g(G_1) + g(G_2) = g$.

* $G$ can be obtained by insertion of a separating dipole, a separating ladder, or a two-edge-connection in between: $\ell=1$, connected, and melon-free Feynman graphs $G_1$ and $G_2$, such that $g(G_1) + g(G_2) = g$.

We prove by generalizing the arguments of Theorem <ref>.

Let us consider $\ell(G)=1$ first.

($\boldsymbol{\ell=1}$, 2PI.)
If $G$ is 2PI, there exists a connecting N-dipole in $G$, which can be maximally extended. Contracting the resulting N-dipole or N-ladder $X$ yields a
$\ell=1$ Feynman graph $G'$ of genus $g(G') = g-1$. Furthermore, $G'$ is necessarily melon-free because the three configurations of Figure <ref> are all excluded: configuration <ref> because $X$ is maximal,
configurations <ref> and <ref> because $G$ should be 2PI but <ref> and <ref> necessarily give $G$ to be 2PR.
This proves the first part of the proposition.

($\boldsymbol{\ell=1}$, 2PR.)
Let us suppose that $G$ is 2PR, and discuss two distinct situations:

-Suppose first that $G$ does not contain a separating dipole. Since $G$ is 2PR, it must still contain a two-edge-cut $(e,e')$. By Lemma <ref>, performing a flip on $(e,e')$ yields two Feynman graphs $G_1$ and $G_2$ such that
$\ell(G_1) =1$, $\ell(G_2) = 0$ without the loss of generality.
However, we cannot have $g(G_2) =0 $, because then it is not allowed by the definition of the two-edge-cut. Therefore,
$g(G_1) < g$ and $g(G_1) + g(G_2) = g$.
As in Theorem <ref>, $G_1$ and $G_2$ are necessarily melon-free,
otherwise it would imply that there was a separating dipole in $G$
or that $G$ was not melon-free to begin with.

-Assume instead that $G$ contains a separating dipole. As in Theorem <ref>, we proceed to contracting its maximal extension $X$, itself a separating dipole or a separating ladder. The two resulting
Feynman graphs $G_1$ with $\ell(G_1) = 1$ and $G_2$  with $\ell(G_2) = 0$ are again melon-free. However, again $g(G_2) =0$ is excluded because then, it means that $G$ has a melon.
Therefore, they obey: $g(G_1) < g$ and $g(G_1) + g(G_2) = g$.

This concludes the proof for $\ell(G) = 1$.

Let us now consider $\ell(G)=2$.

($\boldsymbol{\ell=2}$, 2PI.)
If $G$ is 2PI, there exists either

* a connecting N-dipole in $G$, which can be maximally extended, or

* a rearranging N-dipole in $G$, which can be maximally extended.

Furthermore, the consequences of the both cases above follow.
Contracting the resulting connecting (resp. rearranging) N-dipole or N-ladder (in Figure <ref> they may be denoted as $X$ (resp. $X$ or $\tilde X$))  yields a  Feynman graph $G'$ of genus $g(G') = g-1 \ge 1$ with $\ell=2$ (resp. $\ell=0$). Furthermore, $G'$ is necessarily melon-free because the three configurations of Figure <ref> are all excluded: configuration <ref> because $X$ is maximal,
configurations <ref> and <ref> because $G$ should be 2PI by assumption but <ref> and <ref> necessarily give $G$ to be 2PR.

($\boldsymbol{\ell=2}$, 2PR.)
Let us suppose that $G$ is 2PR. We shall distinguish two cases:

* $G$ does not contain a separating dipole. Since $G$ is 2PR, it must still contain a two-edge-cut $(e,e')$. By Lemma <ref>, performing a flip on $(e,e')$ yields two Feynman graphs $G_1$ and $G_2$.

* $G$ contains a separating dipole. As in Theorem <ref>, we proceed to contracting its maximal extension $X$, itself a separating dipole or a separating ladder, which will result in the two resulting Feynman graphs $G_1$ and $G_2$.

In both of the cases above, without a loss of generality, $G_1$ and $G_2$ will obey either cases:

* $\ell(G_1) = 2$, $\ell (G_2) =0$. However, we cannot have $g(G_2) =0 $,

- for the case $G$ does not contain a separating dipole, it is not allowed by the definition of the two-edge-cut.

- for the case $G$ contains a separating dipole, it means that $G$ had a melon.

Therefore,   $g(G_1) < g$  and $g(G_1) + g(G_2) = g$.

* $\ell (G_1) = 1$, $\ell (G_2) = 1$. And, $g(G_1) + g(G_2) = g$.

The Theorem <ref> is a key result of this paper.
It provides a constructive way of generating all the $\ell=1$ and $\ell=2$ Feynman graphs, order by order in the genus and starting at genus one, by application of the following algorithms.

Algorithmic construction of all
$\ell=1, 2$ graphs.

* Assume that the set
$\hat{E}_{g', \, \ell=1}$ (resp. $\hat{E}_{g', \, \ell=2}$)
melon-free Feynman graphs of genus $g'\leq g-1$ has been constructed. Additionally, note that in <cit.>, we have already constructed the set $\hat{E}_{g', \, \ell=0}$, $\forall g' \le 0$, which is necessary to construct all $\ell = 2$ graphs;

* Construct the set $\hat{E}^\mathrm{2PI}_{g, \, \ell=1}$ (resp. $\hat{E}^\mathrm{2PI}_{g, \, \ell=2}$) of 2PI melon-free Feynman graphs of genus $g$, by inserting a connecting N-dipole or N-ladder into any element of $\hat{E}_{g-1, \, \ell=1}$,
(resp. by inserting either

* a connecting N-dipole or N-ladder into any element of $\hat{E}_{g-1, \, \ell=2}$, or

* a rearranging N-dipole or N-ladder into any element of $\hat{E}_{g-1, \, \ell=0}$,)

in any possible way that yields a 2PI graph.
Pay attention that it is possible that the graph before the insertion is 2PR, yielding a 2PI graph.
Therefore, it is necessary to start from elements of $\hat{E}$ as opposed to $\hat{E}^\mathrm{2PI}$ for both $\ell =1$ and $\ell=2$;

* Construct the set $\hat{E}^\mathrm{2PR}_{g, \, \ell = 1}$ (resp. $\hat{E}^\mathrm{2PR}_{g, \, \ell = 2}$) of 2PR  melon-free Feynman graphs by inserting
a separating dipole, a separating ladder, or a two-edge-connection
in between any element of $\hat{E}_{g_1, \ell_1=1}$ and $\hat{E}_{g_2, \ell_2 = 0}$ such that $g_1 + g_2 = g$ and $g_1 < g$
(resp. in between any element of either

* $\hat{E}_{g_1, \ell_1=2}$ and $\hat{E}_{g_2, \ell_2 = 0}$ such that $g_1 + g_2 = g$ and $g_1 < g$, or

* $\hat{E}_{g_1, \ell_1=1}$ and $\hat{E}_{g_2, \ell_2 = 1}$ such that $g_1 + g_2 = g$)
in any possible way.

* Obtain the set
$\hat{E}_{g, \, \ell=1} = \hat{E}^\mathrm{2PR}_{g, \, \ell=1} \cup \hat{E}^\mathrm{2PI}_{g, \, \ell=1}$
(resp. $\hat{E}_{g, \, \ell=2} = \hat{E}^\mathrm{2PR}_{g, \, \ell=2} \cup \hat{E}^\mathrm{2PI}_{g, \, \ell=2}$ )
of all melon-free Feynman graphs of genus $g$;

* Finally, insert arbitrary melonic
Feynman graphs on the edges of any element in
$\hat{E}_{g, \, \ell=1}$ (resp. $\hat{E}_{g, \, \ell=2}$ )
to obtain the set
$E_{g, \, \ell=1}$ (resp. $E_{g, \, \ell=2}$)
Feynman graphs (see the fourth bullet in Remark <ref>).

§ CLASSIFICATION FOR $\ELL=3$ WITH $G=0$

This discussion follows a similar approach as in the planar case for $\ell =1$ and $\ell =2$.
By plugging $\ell=3$, $g=0$ in equation (<ref>), we obtain the following relation

\begin{align}
\varphi = \frac{v-1}{2}.
\end{align}

This relation implies that the number of vertices should be odd.

For each graph with $\ell=3$, $g=0$, it either contains at least one $\oD$-loop of length $2$ or has $\oD$-loop configuration $(4,4,\ldots,4,6)$.

The proof is very similar to the proof of
Lemma <ref>.
Consider a planar graph with $\ell=3$ that does not contain an $\oD$-loop of length two and does not have $\oD$-loop configuration $(4,4,\ldots,4,6)$.  Then because  $l_i$ is even, the smallest possible $e$ is obtained when $e= 4\varphi$ or $e= 4\varphi + 4$. These expressions of $e$ give successively the following two equations:

\begin{eqnarray}
&&e = 4\varphi = 4(\frac{v-1}{2}) = 2v - 2 < 2v,\cr
&&e = 4\varphi + 4 = 4(\frac{v-1}{2}) + 4 = 2v + 2 > 2v.
\end{eqnarray}

Because the graphs we are considering are $4$-regular, we have that $e=2v$.
This gives a contradiction in both cases, hence the statement is proved.

In the following, we should distinguish different embedding of a tadpole as illustrated in Figure <ref>.

Example of distinct tadpole (labelled by $e$) embedding.

All possible 2PR schemes for $\ell=3$, $g=0$, up to tadpole embedding and up to orientations of edges.
$\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$.
$X \in \{$I-dipole$, \, $O-dipole$, \, $N-dipole$, \, {\rm N}_ {\rm e},\,{\rm N}_{\rm o},\,{\rm I},\,{\rm O},\,{\rm B}\}$.

Including the orientations of the edges, for  $\ell=3$ and $g=0$, there are four 2PI schemes as listed in Figure <ref>.
Up to tadpole embedding and orientations of the edges, all the 2PR schemes are listed in Figure <ref>.

All possible 2PI schemes for $\ell=3$, $g=0$.
$\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$.

In the proof, we ignore the tadpole embedding and the orientations of the edges, as they can be recovered paying attention to the definition of graph/scheme isomorphism given in Definition <ref>.

Consider a planar graph with $\ell=3$.
If an $\oD$-loop of length two is present, we can remove iteratively the $\oD$-loops of length two, while keeping $\ell$ and $g$ invariant, as described in Figure <ref>.
The resulting graph does not have any $\oD$-loops of length $2$ and hence should have $\oD$-loop configuration $(4,4,\ldots,4,6)$, as explained in
Lemma <ref>.
By reversing this argument we can conclude that every graph is constructed from $(4,4,\ldots,4,6)$ graphs by consecutively adding $\oD$-loops of length of $2$. All possible $\oD$-loops of length $4$ are discussed in the proof of Theorem <ref>. We now study the $\oD$-loops of length $6$, which are found empirically (a different proof is addressed in Theorem <ref>).

An $\oD$-loop of length six contains at least three vertices. In this minimal case, there are three possibilities depicted in  Figure <ref>.
The first two graphs are similar to the ones displayed in Figure <ref>. They can be constructed from the cycle graph by adding three tadpoles. The third graph stands out, as it does not have a tadpole.

$\oD$-loops of length $6$ containing $3$ vertices.

Secondly, suppose the $\oD$-loop contains four vertices. Then, the only possible graphs are the ones in Figure <ref>, up to tadpoles orientations. Because they must contain a tadpole, they can be formed from the first two $\oD$-loops of length $4$ in Figure <ref> by adding a tadpole.

$\oD$-loops of length $6$ containing $4$ vertices.

Thirdly, suppose the $\oD$-loop contains five vertices. Then, when the $\oD$-loop contains a tadpole, it can be formed by adding a tadpole to the $\oD$-loop on the right of Figure <ref>. The resulting $\oD$-loop is displayed on the left hand side in Figure <ref>. When there are no tadpoles present, the only possibilities are given in the middle and on the right of Figure <ref>.
In the case for planar graphs with $\ell=3$, these latter two subgraphs are equivalent.

$\oD$-loops of length $6$ containing $5$ vertices.

Finally, suppose the $\oD$-loop contains six vertices.
Then the only possible $\oD$-loop one can form is the subgraph drawn in <ref>.

An $\oD$-loop of length $6$ containing $6$ vertices.

We now have described all the possible configurations for $\oD$-loops with length $6$. The graphs in question are constructed by adding $\oD$-loops of length $4$ to the $\oD$-loop with length $6$, as was done in the case for $\ell =2$ in Figure <ref>.
We distinguish three cases.

Suppose that the $\oD$-loop of length six is of the form as in Figure <ref>. Then the procedure of adding $\oD$-loops of length $4$ is identical to the case where $\ell=2$, as described in Figure <ref>. As discussed earlier it results in a ladder with only I- and/or O-dipoles ending in a tadpole. The possible graphs
are given in Figure <ref>.

Graphs with $\ell=3$ and $g=0$ and $\oD$-loop structure  $(4,4,\ldots,4,6)$, where the $\oD$-loop of length $6$ contains $4$ vertices.
$ X\in\{$I-dipole$, \,$O-dipole$,\, {\rm I}, {\rm O, {\rm B}^*}\}$, where ${\rm B}^*$ is a particular B-ladder-vertex which only contains I-dipoles and O-dipoles.

Suppose that the $\oD$-loop of length six is of the form as in Figure <ref>. Then the procedure of adding $\oD$-loops of length $4$ is nearly identical to the case where $\ell=2$.
Either one can add only $\oD$-loops of length four without a tadpole that make a closed chain as in graphs drawn on the top row of Figure <ref>, or one performs the procedure explained
around Figure <ref>,
resulting in ladders containing only  I- or O-dipoles ending in a tadpole. The resulting graphs can be found in Figure <ref>.

with $\ell=3$ and $g=0$ and $\oD$-loop structure  $(4,4,\ldots,4,6)$, where the $\oD$-loop of length $6$ contains $5$ vertices.
$ X\in\{$I-dipole$, \,$O-dipole$,\, {\rm I}, {\rm O}, {\rm B}^*\}$, where ${\rm B}^*$ is a broken ladder of a type which contains only I- and O-dipoles.
$\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$.
Only the left top one is 2PI, and the rest of the four schemes shown are 2PR.

Suppose now the case where the $\oD$-loop of length $6$ is as in Figure <ref>.
Then, there are only three possibilities,
to add $\oD$-loops of length $4$.
In Figure <ref>  we indicate the vertices and corresponding half-edges that can be contained in the same $\oD$-loop of length $4$ with the same color.

In the first case in Figure <ref>,
there is only one possible configuration for the $\oD$-loops added at the red and green half-edges.
We then add $\oD$-loops of length $4$ to the the blue half-edges, following the same procedure
as described in Figure <ref>.
We end up with the third graph in Figure <ref>.

In the second case
depicted in Figure <ref>, we carry out the procedure of adding $\oD$-loops of length $4$ to the red, green and blue half-edges respectively.
We have two possibilities.
First possibility is
each procedure ends by adding an  $\oD$-loop of length $4$ with a tadpole.
Then we end up with the fourth graph in Figure <ref>.
Otherwise, one of the procedures (say, starting with red) ends with an $\oD$-loop with a tadpole, while the other two procedures (say, starting at green, and at blue)
together to make a closed chain, similar as to what was depicted in Figure <ref>.
We then end up with the second graph in Figure <ref>.

the third case
in Figure <ref> is slightly more subtle.
We again perform the procedure of adding $\oD$-loops of length $4$ to the red, green and blue half-edges respectively.
Again, each procedure
of adding $\oD$-loops of length $4$
can end by adding an $\oD$-loop with a tadpole.
Then we end up with the fifth graph in Figure <ref>.
Now we consider how two procedures
of adding $\oD$-loops of length $4$
starting at two different sets of colored half-edges
to make a closed chain as in the previous case.
In this case we are more restricted how such a closed chain can occur.
Indeed, the procedure of adding $\oD$-loops starting at the blue half-edges cannot
be connected
together with the procedure starting at the red half-edges, as this would make it impossible to add an  $\oD$-loop to the green half-edges while keeping the graph planar.
However, the procedure
of adding $\oD$-loops
starting at the green half-edges can
be connected
together with the procedure started at either the red or blue half-edges.
One can check we then end up with a graph equivalent to the first graph in Figure <ref>.

Possible ways of adding $\oD$-loops of length $4$ to this particular $\oD$-loop of length $6$.

Schemes with $\ell=3$ and $g=0$ and $\oD$-loop structure  $(4,4,\ldots,4,6)$, where the $\oD$-loop of length $6$ contains $6$ vertices.
$\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$, and
$ X\in\{$I-dipole$, \,$O-dipole$,\, {\rm I}, {\rm O}, {\rm B}^*\}$, where ${\rm B}^*$ is a broken ladder of a type which contains only I- and O-dipoles.

The next step of this proof is similar to the proof for $\ell=2$.
As discussed before, one can construct general planar graphs with $\ell=3$ from the $(4,4,\ldots,4,6)$ graphs by adding $\oD$-loops of length $2$ that do not change the genus. In the case where there are no tadpoles present, such $\oD$-loops will be melons. In the case where tadpoles are present, adding such non-melonic $\oD$-loops, amounts to adding N-dipoles to the, possibly empty, ladder.

To summarize, all the melon-free schemes with $g=0$ and $\ell=3$, ignoring the orientations of the edges, are given in Figure <ref>.
Recovering the orientations of the edges only for 2PI schemes (the two schemes on the top row in Figure <ref>, we list all the 2PI schemes for $g=0$ and $\ell=3$ in Figure <ref>.

All possible schemes for $\ell=3$, $g=0$.
$\widetilde {\rm I}\in \{ $I-dipole$, \,{\rm I}\}$, and
$X \in \{$I-dipole$, \, $O-dipole$, \, $N-dipole$, \, {\rm N}_ {\rm e},\,{\rm N}_{\rm o},\,{\rm I},\,{\rm O},\,{\rm B}\}$.
Top row are 2PI schemes, and the rest are 2PR.
Note that if we replace the I-vertex with an I-dipole in the left scheme on the top row, then the graph is isomorphic to the right graph on the top row.
Similarly, if we replace the I-vertex with an I-dipole in the middle scheme on the middle row, then the graph is isomorphic to the right graph on the middle row with one of the ladder-vertices being empty.

§ TOWARD CLASSIFICATION OF $\ELL> 3$ WITH $G=0$

This section will cover the enumeration of 2PI melon-free graphs with grade $\ell$ greater than $3$. More precisely, we find all graphs with $\oD$-loop configurations $(4, 4, \dots, 2\ell)$ for $\ell=4,5, 6$. We finally deduce how to enumerate the 2PI melon-free graphs with a single $\oD$-loop and arbitrary grade after connecting to alternating knots.

Let us denote by $p_i$ (an even number) and $p(n,m)=(p_1, \ldots, p_m)$ a partition of $n$ in $m$ elements with $n=\sum_{i=1}^m p_i$ and by $p(n,m)^{>k}$ a partition in which each $p_i$ is greater than $k$.

Let $G$ be a graph with grade $\ell$ and $\varphi$ number of $\oD$-loops.

* If $\ell>\varphi + 2$ then $G$ has $\oD$-loop configurations $p(2(l+2i),i+1)$; $i=0, \ldots, \ell-4$;

* Else, $G$ contains an $\oD$-loop of length $2$ or has $\oD$-loop configurations of the form $(4, 4, \ldots, 4, p(2(\ell+2(i-1)),i)^{>2})$; $i=1, \ldots, \ell-2$.

For $\ell>\varphi + 2$, $\varphi$ is clearly at most $\ell-3$ and therefore any $\oD$-loop configuration is a partition of $E$ in 1, 2, $\ldots$ or $\ell-3$ elements. Then $\varphi=i+1$ in the first equation in (<ref>) gives $E=2v=2\ell-4+4(i+1)=2(\ell+2i)$ ending the proof of 1).

We now assume that $\ell\leq \varphi + 2$ and $G$ contains no $\oD$-loop of length $2$. The smallest value of $E$ is obtained if every $\oD$-loop but the fewest possible has length $4$. The maximum number $m$ of $\oD$-loops with length greater than $4$ is at most $\ell-2$. Otherwise if $m>\ell-2$ then $E=4(\varphi-m)+\sum_{t=1}^ml_i$ with $l_i\geq 6$ for all $i$. Then $E=2v\geq 4(\varphi-m)+6m=4\varphi+2m>4+2v-2\ell+2\ell-4=2v$ which gives a contradiction.

If the $\oD$-loop configuration
has only one element $p_k >4$, then it is of the form $(4, 4, \ldots, 4, 2\ell)$. In fact $E=2v=4(\varphi-1)+k=4(\frac{v}{2}-\frac{\ell}{2})+k=2v-2\ell+k$ and therefore $k=2\ell$. More generally, if there are $1\leq i\leq \ell-2$ elements; $l_1, \ldots, l_i$ of length greater than $4$, then $\sum_{t=1}^il_t=2(\ell+2(i-1))$. In fact, $E=2v=4(\varphi-i)+\sum_{t=1}^il_t=4(1+\frac{v}{2}-\frac{\ell}{2}-i)+\sum_{t=1}^il_t=4+2v-2\ell-4i+\sum_{t=1}^il_t$ implies that $\sum_{t=1}^il_t=2(\ell+2(i-1))$.

From now on, we skip the orientation in the enumeration of the schemes for simplicity.
One can recover the information encoded in the orientation by assigning orientations of edges in a graph and making sure that no graphs are isomorphic by following Definition <ref>.

Let us now discuss the particular cases of $\ell=4,5,6$ in which we only address the $\oD$-loops of length greater than two.

Case $\ell=4$:
In case $\ell>\varphi+2$, then $\varphi=1$ and the only $\oD$-loop configuration is $(8)=p(2\times 4,1)$. Otherwise the only $\oD$-loop configurations are $(4, 4, \ldots, 4, p(2(4+2(i-1)),i)^{>2})$; $i=1,2$ namely $(4, 4, \ldots, 4, 8)$
and $(4, 4, \ldots,4, 6, 6)$. A graphical representations of these is given in Figures <ref> and <ref>.

Some schematic representation of $\ell=4$ and $\varphi=1$ graphs.

Some schematic representations of $\ell=4$ and $\varphi=2$ graphs.

Case $\ell=5$:
For $\ell>\varphi+2$, then $\varphi=1,2$ and the case $\varphi=1$ gives the only $\oD$-loop configuration is $(10)$ while $\varphi=2$ gives two $\oD$-loop configurations of $(6,8)$ and $(4,10)$.
Assume that $\ell\leq\varphi+2$. The only $\oD$-loop configurations are $(4, 4, \ldots, 4, 10)$, $(4, 4, \ldots, 4, 6, 8)$
and $(4, 4, \ldots,4, 6, 6, 6)$. An illustration for the existence of $\oD$-loop configurations of the form $(10)$ are given in Figure <ref> and those of $(6,8)$ and $(4,6,8)$ are respectively the first two figures in <ref>.

Some schematic representations of $\ell=5$ and $\varphi=1$ graphs.

Case $\ell=6$:
Assuming that $\ell>\varphi+2$, $\varphi=1,2,3$ and the case $\varphi=1$ gives the only $\oD$-loop configuration of $(12)$. The case $\varphi=2$ gives three $\oD$-loop configurations of $(6,10)$, $(8,8)$ and $(4,12)$ while $\varphi=3$ gives $(4,4,12)$, $(4,6,10)$, $(4,8,8)$ and $(6,6,8)$.
Suppose that $\ell\leq\varphi+2$. The only $\oD$-loop configurations are $(4, 4, \ldots, 4, 12)$, $(4, 4, \ldots, 4, 6, 10)$, $(4, 4, \ldots, 4, 8, 8)$ and $(4, 4, \ldots, 4, 6, 6, 8)$. An illustration for the existence of $(6,10)$, $(6,6,8)$ are the third  and forth graphs in Figure <ref>.

Schematic representations of the configurations $(6,8)$ and $(4,6,8)$ for $\ell=5$ followed by $(6,10)$ and $(6,6,8)$ for $\ell=6$ (reading from left to right).

The proof of constructing graphs with  $\oD$-loop configurations $(6)$ and $(4,4,\dots,6)$  for $l=3$ is performed differently as compared to the proof in Theorem <ref> for the 2PI graphs in the following Theorem <ref>.
This proof in Theorem<ref> can also be extended to generate 2PR graphs and is easily generalizable to higher $\ell >3$.

A necklace graph with $n$ vertices is the cyclic graph with $n$ vertices in which every edge is doubled.

An illustration of a necklace graph with 5 vertices is given by the leftmost graph in the bottom row in Figure <ref>.

Let $G$ be a connected 2PI melon-free Feynman graph with grade $\ell$.

* If $\ell=3$, $G$ has $\oD$-loop configuration $(6)$ whose only representation is the necklace graph or the configuration $(4,4,\dots, 6)$ which form is illustrated on the left hand side of Figure <ref>.

* If $\ell= 4$, the graph $G$ has $\oD$-loop configuration $(8)$ (given by the graph 2 in Figure <ref>) or $(4,4,\dots, 8)$  with the form illustrated on the right hand side of Figure <ref>.

* If $\ell= 5$ and the graph $G$ has $\oD$-loop configuration $(10)$, then it is given by the necklace graph or the graph 4 in Figure <ref>.

* If $\ell= 6$ and the graph $G$ has $\oD$-loop configuration $(12)$, then it is given by the second graph in Figure <ref>, the three graphs in Figure <ref> the third graph in Figure <ref>, the second graph in Figures <ref> and <ref>
and the last graphs in the figures <ref>  <ref>).

Graphs with loop configurations $(4, 4, \ldots, 6)$ and $(4, 4, \ldots, 8).$

Assume that $\ell= 3$ and $g = 0$. The $\oD$-loop configurations in this case are $(6)$, or $(4, 4, \dots, 4, 6)$. We can prove that the only graph with $\oD$-loop configuration $(6)$ is the
necklace graph.
Indeed, let $V$, $E$ and $F$ be respectively the number of vertices, edges and faces (corresponding to left or right faces in this context) of the graph $G$ and $v$ (respectively $f$) be a vertex (respectively a face) of $G$. Clearly $\sum_vdeg(v)=2E$ implies that $E=2V$ because the graph is 4-regular. The graph $G$ contains a triangular face otherwise all the faces are $2$-gon since the graph is a tadpole free graph. Suppose all the faces are $2$-gon. This implies that $\sum_fdeg(f)=2F=2E$  and using the Euler formula it follows that $V-2V+2V=2$ and then $V=2$, which is not true since $G$ has three vertices (replacing $\ell=3$ in (<ref>)). There is only one way to connect the two half-edges attached to each vertex of this triangle giving therefore the necklace graph.

Let us now look at the $\oD$-loop configuration of the form $(4, 6)$. In this case, the number of vertices is $5$ and the $4$-edge $\oD$-loop cannot only use two vertices otherwise there should be a self loop and also the graph will be disconnected. Neither the $4$-edge $\oD$-loop can only use three vertices without forming a tadpole or self-loop. Therefore the only possibility is that the $4$ edge $\oD$-loop should connect $4$ vertices in the form of Figure <ref>.

Representation of a $4$-edge $\oD$-loop.

The fifth vertex can only be connected to the half edges $A$, $B$, $C$ and $D$ or to the half edges $E$, $F$, $G$ and $H$ and both cases give isomorphism graphs. Assume that this vertex is connected to the half edges $A$, $B$, $C$ and $D$. The half-edge $E$ can only be connected to $F$ or $G$ otherwise the resulting graph can not be planar and the same applies to the other half edges $F$, $G$ and $H$. The final result is given by the graph in Figure <ref> ending therefore the proof for the configuration $(4, 6)$.

Representation of the configuration $(4, 6)$.

Let us now look at the configuration $(4, 4, 6)$. Here the number of vertices is $7$ and a $4$-edge loop is formed as given in
Figure <ref>. The second $4$-edge loop in this configuration can not be formed only with the four vertices of this graph otherwise the graphs will be disconnected. Furthermore any $\oD$-loop should use an even number of these vertices. Therefore the second 4-edge $\oD$-loop can only be obtained by taking two of the vertices used by the previous 4-edge $\oD$-loop giving the two representations in Figure <ref>.

Schematic representations toward the configuration $(4, 4, 6)$.

The representation on left hand side is impossible because the half-edges $B$ and $E$ can not be connected to any other without creating a non planar graph. Therefore we have the representation on the right hand side which implies that we should join $B$ to $F$ and $G$ to $H$. The only vertex left will then join the remaining four half-edges giving the expected graph.

We now turn our attention to the configuration $(4, 4, 4, 6)$. Following the previous proof there are two $4$-edge $\oD$-loop which are connected and given as in the graph on the right hand side in Figure <ref>. Otherwise the three 4-edge $\oD$-loop would be separated needing therefore more than 9 vertices. The third 4-edge loop can only be built by using two new vertices and the half-edges $A$, $B$, $E$ and $F$ or  $D$, $C$, $H$ and $G$. Finally the remaining 4 half edges in the resulting graph will be connected to the last vertex.

This recursive procedure can be extended for a general configuration of the form $(4, 4, \dots, 4, 6)$.

Assume that $\ell=4$. In case there is a face of length 4, it is not hard to see that the graph either has tadpole or more than one $\oD$-loop. Proceeding in the same way as in the $\ell=3$ case shows that the graph has a triangular face. Since it is a connected graph, we have the following the form of Graph 1 in Figure <ref>. The half-edge $C$ of this figure can only be connected to $B$ or $H$ otherwise we will create a tadpole or putting an odd number of half-edge in a face violating therefore the planarity of the graph. If it is connected to $B$ then we have the following connections:$A$ to $D$, $E$ to $F$ and $H$ to $G$ giving the Graph 2 in Figure <ref>. In case $C$ is connected to $H$, the half-edge $B$ can only be connected to $A$ and the connections $E$ to $F$ and $D$ to $G$ follow to avoid tadpole or having an odd number of half-edges in a face. It is not hard to see that both results give isomorphic graphs. A similar recursive procedure to the case $l=3$ gives the graphs with configurations $(4,\ldots,4,8)$.

Schematic representations of $\ell=4, 5$ and $\varphi=1$ graph.

Representations with face of length at least 3; $\ell=4$ and $\varphi=1$.

We now turn to the case $\ell=5$. Assume that the graph $G$ has only faces of length 2 or 3 and the number of such faces is denoted by $F_i$; $i=2, 3$. The Euler formula gives $V-2V+F_2+\frac{2}{3}(E-F_2)=2$ which implies that $F_2=1$ since $V=5$. The graph $G$ should therefore contain only one face of length $2$ and all the remaining are of length $3$. It is therefore of the form of Graph 1 in Figure <ref> to which we should add one more vertex and connect the remaining half edges. We should already connect $E$ to $F$ to avoid having a face of length longer than 3 and there are exactly two non isomorphic possibilities to add the only remaining vertex giving the two graphs in Figure <ref>. Consider the Graph 1 in this figure. The half-edges $F$ and $G$ should be linked connecting therefore $E$ and $H$. If we link $D$ to $C$ then $A$ should go to $B$ giving a contradiction because this will create two faces of length 2. We should therefore link $D$ to $A$ and then $B$ to $C$ which is also another contradiction since this will create a face of length 4 ($ABCD$). We now consider Graph 2 of the same figure. We should link $A$ to $B$ and $E$ to $D$. this implies that $F$ can only go to $G$ or $C$ (implying that $H$ connects $C$ or $G$ respectively) giving in both cases two faces of length 2. This is the final contradiction. So in any case we can not construct a graph in such a way that all the faces are of length 2 or 3. The graph $G$ therefore contains a face of length 4 or 5.

Assume that there is a face of length 5. It is not hard to prove that the result is necessarly the necklace graph. We now assume that there is a quadrilateral face in $G$. Since $G$ is a connected graph, we have the form of the Graph 3 in Figure <ref>. The half-edge $C$ of this figure can only be connected to $B$, $H$ or $J$ otherwise we will create a tadpole or putting an odd number of half-edges in a face violating therefore the planarity of $G$. Assume that we want to avoid having more than one $\oD$-loop, avoid having tadpole or an even number of half-edges in a face. Based on this, the half-edge $C$ can not connect $J$ without giving a contradiction.  Assume that $C$ is connected to $H$, the half-edge $D$ can only be connected to $G$ and the connections $E$ to $F$, $A$ to $B$ and $I$ to $F$ follow, given the graph Graph 4 in Figure <ref>. If we connect $C$ to $B$, then $D$ should be connected to $A$, $E$ to $F$, $G$ to $H$ and $I$ to $J$ resulting in a graph isomorphic to the graph Graph 4 in Figure <ref>.
Finally we got a unique representation given by Graph 4 in Figure <ref>.

Schematic representations with a face of length 6; $\ell=6$ and $\varphi=1$ graph.

Consider the case where $\ell=6$. Assume that the graph $G$ has a face of length $6$. This gives the first configuration in Figure <ref> (reading from left to right). The half edge $A$ can not be connected to $B$, $C$, $D$, $E$, $G$, $H$, $I$, $J$ or $K$. Indeed, connecting $A$ to $B$ will generate a tadpole and in the same way connecting $A$ to $J$ will join $L$ to $K$ which is a tadpole as well. If we connect $A$ to $C$, $E$, $G$ or $I$ it will generate an odd number of half edges in a face. Connecting $A$ to $D$ gives the $\oD$-loop of length 2 (between $A$ and $D$) making therefore the graph to have more than one $\oD$-loop. Linking $A$ to $H$ will join $L$ to $K$, $J$ or $I$ since the graph is planar. If we connect the half edge $L$ to $K$, that will generate a tadpole. Sending $L$ to $J$ is impossible because that will put a single half edge $K$ alone in a face and therefore $L$ should go to $I$ which is also impossible because this will give one more $\oD$-loop of length 2 (between $L$ and $I$). Thus $A$ can only be connected to $F$ or $L$. Assume that we want to avoid having more than one $\oD$-loop, having tadpole or an even number of half-edges in a face. If $A$ connects $F$, then due these reasons, we should join $B$ to $C$ and $D$ to $E$. In the same way we should necessarily connect $L$ to $G$, $K$ to $J$ and $I$ to $H$ giving the second graph in Figure <ref> that we named $G_1$ in the following. If we assume that $A$ is connected to $L$, then for the same reasons listed earlier, the half edge $B$ can not connect $D$, $E$, $F$, $G$, $H$, $J$ or $K$. Therefore we can only join $B$ to $C$ or $I$. If $B$ connects $C$ then $D$ should go to $K$. Indeed due to the same reasons listed earlier $D$ can not connect $F$, $G$, $H$, $I$ and $J$. Furthermore, sending $D$ to $E$ will connect $F$ to $G$, $H$ to $I$ and $J$ to $K$ giving therefore a graph with two $\oD$-loops.  In the same way $E$ should go to $J$, $F$ to $G$ and $H$ to $I$ giving a graph isomorphic to $G_1$.

Configurations with a face of length 5; $\ell=6$ and $\varphi=1$ graph.

Let us now assume that there is a face of length $5$ and no face of higher length. The only vertex left (not used in the face) is connected to one of the half edge giving the third configuration represented in Figure <ref>. Once again, assume that we want to avoid having more than one $\oD$-loop, having tadpole or an even number of half-edges in a face. Proceeding in the same way as earlier, the half edge $A$ can not be connected to $C$, $D$, $E$, $F$, $G$, $H$, $I$, $J$ or $K$. Therefore we can only connect $A$ to $B$ or $L$.

Assume that $A$ is linked to $B$. The half edge $C$ can only connect $F$ or $L$. In the first case $D$ should be connected to $E$, $G$ to $L$, $K$ to $J$ and $I$ to $H$, giving the first graph in Figure <ref> that we will call $G_2$ in the following.
Consider now the second case where $C$ is connected to $L$. The half-edge $D$ can only connect $E$ or $K$. If $D$ joins $E$ then $F$ should go to $G$, $K$ to $J$ and $I$ to $H$ giving the second graph in Figure <ref> that we will call $G_3$. Connecting $D$ to $K$ will imply that $E$ should be connected to $J$, $I$ to $H$ and $F$ to $G$. This gives a graph isomorphic to $G_2$.

Assume now that $A$ is connected to $L$. The half-edge $B$ should therefore go to $G$, $I$ or $K$. Connecting $B$ to $G$ will send $C$ to $F$, $D$ to $E$, $H$ to $I$ and $J$ to $K$ giving a graph isomorphic to $G_3$. If instead we connect $B$ to $K$, then $C$ should go to $J$, $D$ to $E$, $F$ to $G$ and $H$ to $I$ giving the third graph in Figure <ref> that we will call $G_4$ in the following. Sending $B$ to $I$ and proceeding in the same way as above, we obtain a graph isomorphic to $G_4$.

Configurations with a face  of length 4; $\ell=6$ and $\varphi=1$ graph.

Configurations with a face  of length 4; $\ell=6$ and $\varphi=1$ graph.

Configurations  with a face   of length 4; $\ell=6$ and $\varphi=1$ graph.

Configurations  with a face  of length 4; $\ell=6$ and $\varphi=1$ graph.

Let us now assume that the graph has a face  of length $4$ and no other face has higher length. The remaining two vertices are connected to the square face in eight different configurations: the first configuration in Figure <ref>, the first and third configurations in the figures <ref> and <ref> and the three configurations in Figure <ref>.

Consider now the first configuration in Figure <ref>. The half-edge $F$ should be connected to $G$ (second graph in the same figure), to avoid having a face of length longer than 4. We now assume the same conditions as before by assuming that the resulting graph does not have more than one $\oD$-loop, tadpole or an even number of half-edges in a face. For these reasons, the half-edge $A$ should be connected to $D$, $H$ or $L$. If we connect $A$ to $D$ then $B$ should be connected to $C$. then we must connect $E$ to $H$ or $L$. Connecting $E$ to $H$ is impossible because $L$ should go to $I$ and $K$ to $J$ giving a graph with more than one $\oD$-loops. If $E$ connects $L$ then $H$ goes to $K$ and $I$ to $J$ giving the third graph (named $G_5$) in Figure <ref>. Assume that $A$ is connected to $H$. This implies that $E$ should go to $B$, $C$ to $D$, $L$ to $I$ and $K$ to $J$ giving a graph isomorphic to $G_4$. We now suppose that $A$ connects $L$. The half-edge $B$ should therefore connect $C$, $E$ or $I$. Connecting $B$ to $C$  is impossible because it will send $D$ to $K$, $I$ to $J$ and $H$ to $E$ giving a graph with more that one $\oD$-loops. Connecting $B$ to $E$ is also impossible because $C$ will be connected to $D$, $H$ to $K$ and $I$ to $J$ giving also a graph with more than one $\oD$-loops. We have similar contradiction by sending $B$ to $I$ because $C$ will connect $D$, $E$ will connect $H$ and $K$ will connect $J$.

Let us turn now to the first configuration in Figure <ref>. Similar to the first configuration, the half-edge $A$ should only connect $D$, $F$, $H$ or $L$. Connecting $A$ to $D$ will join $B$ to $C$, $E$ to $H$ or $L$. If we connect $E$ to $H$ then we should join $G$ to $F$, $K$ to $J$ and $I$ to $L$ giving therefore the second graph (named $G_6$) in Figure <ref>. Connecting $E$ to $L$ will send $G$ to $H$, $I$ to $F$ and $J$ to $K$ giving a graph isomorphic to $G_5$.  Assume that $A$ connects $F$. This implies that $B$ should be connected to $E$, $C$ to $D$, $L$ to $I$, $K$ to $J$ and $G$ to $H$ giving a graph isomorphic to $G_2$. It is not possible to connect $A$ to $H$. Because, the planarity implies that $L$ will be connected to $I$, $K$ to $J$, $B$ to $E$, $C$ to $D$ and $F$ to $G$ giving a graph with two $\oD$-loops. We now connect $A$ to $L$. This implies that $B$ should connect $C$, $E$ or $I$. Proceeding in the same way by connecting $B$ to $C$ will send $D$ to $I$ or $K$. If we connect $D$ to $I$ then $F$ should go to $G$, $E$ to $H$, and $J$ to $K$ giving a graph isomorphic to $G_4$. We can not connect $D$ to $K$ because this will join $E$ to $J$, $F$ to $I$ and $G$ to $H$ which is a graph with two $\oD$-loops. Connecting $B$ to $E$ is not possible either because doing so will result by connecting $C$ to $D$, $F$ to $I$, $G$ to $H$ and $J$ to $K$ giving a graph of two $\oD$-loops. We now connect $B$ to $I$. This will connect $C$ to $D$, $E$ to $H$, $F$ to $G$ and $J$ to $K$ which result in a graph isomorphic to $G_5$.

We can now discuss the third configuration of the existence of a face of length 4 in Figure <ref> and work under the condition that the resulting graph does not have more than one $\oD$-loop, tadpole or an even number of half-edges in a face.
The half-edge $A$ can only be connected to $D$, $J$ or $L$. Connecting $A$ to $D$ will join $B$ to $C$ and $E$ to $J$ or $L$. Connecting $E$ to $J$ will join $F$ to $G$, $H$ to $I$ and $K$ to $L$ giving a graph isomorphic to $G_6$. Connecting $E$ to $L$ will send $K$ to $F$, $J$ to $G$ and $I$ to $H$ giving a graph isomorphic to $G_5$. Sending $A$ to $J$ will connect $K$ to $L$. The half-edge $B$ can connect $C$, $E$ or $I$. Connecting $B$ to $C$ is not possible since it will join $D$ to $I$, $E$ to $H$, $F$ to $G$ giving a graph with more  than one $\oD$-loop. Connecting $B$ to $E$ is also impossible because that will connect $C$ to $D$, $F$ to $G$, $H$ to $I$ giving a graph with more than one $\oD$-loop. If we connect $B$ to $I$, then we should join $C$ to $D$, $E$ to $H$ and $F$ to $G$ giving a graph isomorphic to $G_1$. Let us now connect $A$ to $L$. This implies that we should connect $B$ to $C$, $E$ or $K$. Connecting $B$ to $C$ implies that $D$ should go to $K$, $E$ to $J$, $F$ to $G$ and $I$ to $H$ giving a graph isomorphic to $G_4$. If we connect $B$ to $E$, then $C$ should go to $D$, $F$ to $K$, $G$ to $J$ and $H$ to $I$ giving a graph isomorphic to $G_6$.

Let us consider the first configuration in Figure <ref>. Once again we assume the same conditions as before by assuming that the resulting graph (obtained after connecting some half-edges) does not have more than one $\oD$-loop, tadpole or an even number of half-edges in a face. The half-edge $A$ can only connect $B$, $D$ and $L$. If $A$ connects $B$ then $C$ should connect $L$ and $D$ should connect $G$ or $K$. If $D$ connects $K$, then the graph will have more than one $\oD$-loop which is a contradiction. It is not possible to connect $D$ to $G$ because it will imply that $H$ connect $K$ giving a graph with more than one $\oD$-loop. Assume now that $A$ is connected to $D$. In this case $B$ should be connected to $C$ and $E$ to $F$ or $L$. In case we connect $E$ to $F$, then $G$ should be connected to $L$, $H$ to $K$ and $I$ to $J$ giving another contradiction since the resulting graph with gain more than one $\oD$-loops. If we connect $E$ to $L$, then $F$ should be connected to $K$, $G$ to $H$ and $I$ to $J$ giving the second graph (named $G_7$) in Figure <ref>. Assume now that we connect $A$ to $L$. This implies that $B$ should be connected to $C$ or $K$. Sending $B$ to $C$ implies that $D$ will connect $G$ or $K$. Connecting $D$ to $G$ together with a good analysis will create a graph isomorphic to $G_1$. If we connect $D$ to $K$ and make similar analysis then we get a graph with more than one $\oD$-loop (a contradiction).

Let us turn to the third configuration in Figure <ref> and work under the same assumption as earlier. The half edge $A$ can only connect $D$, $F$ or $L$. Connecting $A$ to $D$ implies that $B$ should connect $C$, $E$ should connect $L$ and $F$ will connect $K$ or $G$. If $F$ connects $K$, then $H$ should go to $I$ and $G$ to $J$ giving a contradiction since the resulting graph will gain more than one $\oD$-loops. We can only connect $F$ to $G$ implying that $H$ should be connected to $K$ and $I$ to $J$. This gives a graph isomorphic to $G_6$. Assume that $A$ is connected to $F$. Similar procedure gives a graph isomorphic to $G_1$. Sending $A$ to $L$ will connect $B$ to $C$ or $E$. Connecting $B$ to $C$ is not possible because that will create after similar analysis a graph with two $\oD$-loops. If we connect $B$ to $E$, the same procedure leads to a graph isomorphic to $G_5$.

While still working under the same hypotheses claiming that the resulting graph (obtained after connecting some half-edges) does not have more than one $\oD$-loop, tadpole or an even number of half-edges in a face, we now consider the first configuration given in Figure <ref>. A good analysis shows that we can only connect $A$ to $B$ or $H$. If we join $A$ to $B$ then we should link $C$ to $F$, $J$ or $L$. Connecting $C$ to $F$ will give only one connection to the remaining half edges giving a graph isomorphic to $G_4$. Proceeding in the same way by connecting $C$ to $J$ or $L$ will give a graph isomorphic to $G_7$. In fact, connecting $C$ to $J$ will send $L$ to $K$, $D$ to $E$, $G$ to $H$ and $F$ to $I$. In the same way connecting $C$ to $L$ gives two possibilities: $D$ to $E$ or $K$. If we join $D$ to $E$, then we obtain a graph isomorphic to $G_7$ but the second case gives a graph with more than two $\oD$-loops. Finally connecting $A$ to $H$ and proceeding similarly as above gives a graph with more than one $\oD$-loop which is impossible. Proceeding in the same way for the remaining two configurations in Figure <ref> give either graphs with more than one $\oD$-loops or isomorphic to one of the graphs $G_i$, $i=1, \cdots, 7$.

Configurations  with a face of length 3; $\ell=6$ and $\varphi=1$ graph.

Configurations  with a face of length 3; $\ell=6$ and $\varphi=1$ graph.

Configurations with a face of length 3; $\ell=6$ and $\varphi=1$ graph.

Assume now that the graph has no face of length more than 3. Therefore any face is of length 3 or 2 and we denote by $F_2$ and $F_3$ the number of faces of length 2 and 3 respectively. This leads to the following two equations: $F_2+F_3=8$ (using the Euler characteristic) and $2F_2+3F_3=24$ (using the fact that the sum of the lengths of the faces is two times the number of edges). These equations lead to $F_2=0$ and $F_3=8$ showing that all the faces of the graph are triangular.

Assume that we have the configuration given by a face of length 3 to which we connect one additional vertex given by the first configuration in Figure <ref>. We now need to connect the remaining two vertices but we should already connect the half edge $H$ to $I$ since there is no face of length longer than three given by the second configuration in the same figure. The connection of the fifth vertex gives two possible non isomorphic configurations by the remaining two graphs in Figure <ref>. The third configuration in Figure <ref> implies that we should connect $N$ to $J$ and then $M$ to $A$ giving therefore the first configuration in Figure <ref>. The following two configurations in Figure <ref> are the two possible non isomorphic configurations coming from adding the last vertex to the first configuration of the same figure. Since there is no face of length larger than 3 then these configurations lead to the same graph; the last graph in Figure <ref>. Consider the last configuration in Figure <ref>. We should connect $N$ to $F$ and $L$ to $B$ and the connection of the last vertex gives only one configuration given in the second configuration of Figure <ref>. From this the last graph of the same figure follows.

We could expect to extend some of the results in Theorem <ref> in the following way:
Let $G$ be a connected 2PI melon-free Feynman graph with grade $\ell$. If loop configuration has the form $(4,4,\dots,4, 2\ell)$, its scheme $S_G$ has the form in Figure <ref>.

Some schematic representations of $(4,4,\dots,4, 2\ell)$ with $\ell-2$ crossings.

Unfortunately this only works for $\ell=3,4$. Starting from $l=5$, we could find more configurations as illustrated in Figure <ref>.

Some schematic representations of $(4,4, 10)$.

We can also prove the previous results by relating any of the 4-regular graphs we are studying, to an alternating knot. This is mainly motivated by the following claim: Every four-regular planar graph is the medial graph of some planar graph. For a connected 4-regular planar graph $M$, a planar graph $G$ with $M$ as its medial graph can be constructed as follows. Color the faces of $M$ with only two colors, which is possible because $M$ is Eulerian and thus the dual graph of $M$ is bipartite. The vertices in $G$ correspond to the faces of a single color in $M$. These vertices are linked by an edge for each vertex shared by their corresponding faces in $M$. It should be noted that performing this construction with the faces of the other color as the vertices results in the dual graph of $G$.
Using the checkerboard coloring, the medial graph or 4-regular graph can be associated to an alternating link where each crossing in the link diagram corresponds to a vertex of the graph. This link diagram is an alternating knot for $\varphi=1$.

Using the Rolfsen knot table, there are only one knot with 3 or 4 crossing and two with five crossings. This confirms our results in Proposition <ref> for $\ell=3,4,5$ and $\varphi=1$. In the case case $\ell=6$ and $\varphi=1$ we could expect to get three graphs because there are three knots with 3 crossing in the Table but there are more than that which actually can be obtain by taking the connected sum (because the table only contains prime knots) of two trifoils or applying the Tait flyping moves (the correspondent to Reidemeister moves on 3-spheres). This leads to the following result whose proof is straightforward.

The number of 2PI 4-regular graphs with $\varphi=1$ and $\ell$ is equal to the sum of 1) the number of alternating knots with $\ell$ crossings which are among the prime knots listed in the Rolfsen knot table,  2) the number of knots which are connected sums of these alternating knots, and 3) the number of knots which are obtained after performing the Tait flyping moves.

§ CONCLUSION

In this work, we have classified grade $\ell=1$ and $\ell=2$ with any genus $g$ Feynman graphs generated by a $\uN^2 \times \oD$ multi-matrix model of the type defined by the action (<ref>).
The result is given in Theorem <ref> and Theorem <ref> along with the algorithms on how to recursively construct higher genus graphs for a given $\ell$.
Furthermore, we classified grade $\ell=3$ with $g=0$ planar graphs as given in Theorem <ref>.
We also classified subclasses of higher grade $\ell>3$ planar ($g=0$) graphs in Theorem <ref> and Theorem <ref>.
Theorem <ref> states that a subclass of higher grade $\ell>3$ planar graphs which have one $\oD$-loop ($\varphi = 1$) can be obtained from knot diagrams of Rolfsen table.

One of the main motivations for this work is a possible formulation of topological recursion appearing in this model. In fact, the enumeration of ordinary maps was a major precursor of topological recursion. It was the first enumeration to be shown to be governed by topological recursion, and the theory of topological recursion evolved from the abstraction of loop equations from the theory of matrix models in the specific context of the 1-Hermitian matrix model mentioned above <cit.>.

Tensor models are built on tensor integrals, which are a generalization of matrix integrals. As a result, it is not surprising that tensor models generate Schwinger-Dyson equations that generalize those of matrix models.  Despite advances, solving the Schwinger-Dyson equations for tensor models remains extremely difficult. However, some tensor models can be completely solved in the $1/N$ expansion at any order and still satisfy the topological recursion. This is due to the fact that those tensor models are disguised matrix models, and most recent progress in tensor models relied on a correspondence between tensor models and some multi-matrix models with multi-trace interactions. This allows for the indirect study of tensor models via matrix model techniques on the corresponding matrix models. Thus, in <cit.>, it was demonstrated that the quartic melonic tensor model, after some transformation to a matrix model, satisfies the blobbed topological recursion.

As explained above, the $\uN^2 \times \oD$ model is affine to matrix models, yet it can be readily interpreted as a tensor model.
What is attractive about this model is that there are two parameters owing to different sizes $N$ and $D$, which then let us incrementally classify the graphs as compared to the usual tensor model where only one parameter $N$ controls the classification of the graphs with one parameter Gurau degree $\omega$.
It means that it is more likely that one can classify higher order graphs, as stated earlier.
If one can classify higher order graphs, one may be able to identify topological recursion at play.
This model's affinity to matrix models, indeed giving topological (genus) expansion, is promising to find such a topological recursion.
This will be left to explore in the future.

Additionally, it is interesting to see the critical/continuum limit(s) of the model for the higher $\ell$, as was carried out in <cit.> for $\ell=0$, to see if there is any relevance to quantum gravity (would it give rise to any phases other than branched polymer (tree) or planar?).

Finally, just as in Theorem <ref>, knot theory was useful in classifying subset of graphs of higher $\ell$, can it further help us enumerate more graphs?

§ CONSTRUCTING HIGHER GENUS 2PI GRAPHS

In this Appendix, we illustrate some examples to recursively construct 2PI graphs with given $\ell$ and $g$ from graphs with $\ell$ and $g-1$. Specifically, we focus on constructing 2PI $\ell=2$ and $g=1$ graphs.
In particular, and these examples shown in Figures <ref>, <ref>, <ref>, and <ref> supplement the proof for Theorem <ref>.

We obtain $\ell=2$, $g=1$ 2PI graph by inserting a connecting N (either N-dipole, ${\rm N}_{\rm e}$-ladder-vertex or ${\rm N}_{\rm o}$-ladder-vertex) to $\ell=2$, $g=0$ 2PI graph.
The red scissors indicate where we cut and insert a connecting N, whereas the red dotted lines indicate the $\oD$-loops.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.
See Figure <ref>.

We obtain a $\ell=2$, $g=1$ 2PI graph by inserting a rearranging N to the $\ell=0$, $g=0$ cycle graph.
The red scissors indicate where we cut and insert a connecting N, and the red dotted line indicates the $\oD$ path.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.
See Figure <ref>.

Some examples of how
we obtain $\ell=2$, $g=1$ 2PI graph by inserting a connecting N to $\ell=2$, $g=0$ 2PI graph.
The red scissors indicate where we cut and insert a connecting N, and the red dotted lines indicates the $\oD$ paths.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.
See Figure <ref>.

We show examples of how to obtain $\ell=2$, $g=1$ 2PI graph by inserting a connecting N to $\ell=2$, $g=0$ 2PR graph.
The red scissors indicate where we cut and insert a connecting N, and the red dotted lines indicates the $\oD$ paths.
See Figure <ref>.
We remark that the first scheme we start out with could have $\emptyset$ in place of ${\rm N}_{\rm e}$-ladder-vertex, however, then the resulting scheme will be the same as the first resulting scheme listed in Figure <ref> with I-dipole.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$, {\rm N}_{\rm o}\}$.

§ CONSTRUCTING 2PR GRAPHS OF $\ELL=2$

In this Appendix, we illustrate some examples to recursively construct 2PR graphs of $\ell=2$ and $g=1$.
In particular, and these examples shown in Figures <ref> and <ref> supplement the proof for Theorem <ref>.

Some 2PR schemes of $\ell=2$ and $g=1$ obtained from combining a $\ell=2$ and $g = 0$  graph $G_1$ with a $\ell=0$ and $g=1$ graph $G_2$ via separating dipole or a ladder-vertex
or a two-edge-connection.
These schemes add to Figure <ref>.
$\widetilde {\rm N}_{\rm o} \in \{ $N-dipole$,\, {\rm N}_{\rm o}\}$,
$Y\in\{ $I-dipole$,\, $O-dipole$,\, {\rm N}_{\rm e}, {\rm I}, {\rm O}, {\rm B}\}$.

Some 2PR schemes of $\ell=2$ and $g=1$ obtained from combining a $\ell=1$ and $g = 0$  infinity graph $G_1$ with a $\ell=1$ and $g=1$ graph $G_2$ via separating dipole or a ladder-vertex.
These schemes add to Figure <ref>.
$ X\in\{$N-dipole$, \,$I-dipole$, \,$O-dipole$,\, {\rm N}_{\rm e}, {\rm N}_{\rm o}, {\rm I}, {\rm O}, {\rm B}\}$.

§ CONSTRUCTING ALTERNATING KNOTS CORRESPONDING TO SOME $4$-REGULAR PLANAR GRAPHS

In this section we give some examples of alternating knots that correspond to 4-regular planar graphs. The knot $3_1$ corresponds to the necklace graphs of 3 vertices. The following graphs $4_1$ corresponds to the second graph in Figure <ref>. The knots $5_1$ and $5_2$ correspond to the necklace graphs of 5 vertices and the forth graph in Figure <ref> respectively. Finally the knots $6_1$, $6_1$ and $6_3$ correspond to the first and third graphs in Figure <ref> and the third graph of Figure <ref> respectively.

We should remark that if we perform a connected sum of two knots of the form $3_1$, then the resulting knot corresponds to second graph in Figure <ref>.

Some alternating knots corresponding to $\ell=3,4,5,6$ and $\varphi=1$ graphs.

§ ACKNOWLEDGMENTS

The authors would like to thank Andreani Petrou, Andrew Lobb, Dario Benedetti and Sylvain Carrozza for useful discussions.