Discrete Applied Mathematics 301 (2021) 19–25

Contents lists available at ScienceDirect

Discrete Applied Mathematics

journal homepage: [Link]/locate/dam

On the ratio between the maximum weight of a perfect

matching and the maximum weight of a matching
∗
Giuseppe Mazzuoccolo , Lorenzo Mella
Università degli Studi di Verona, Dipartimento di Informatica, Strada le Grazie 15, 37134 Verona, Italy

article info a b s t r a c t

Article history: Let G be a finite graph (without loops and multiple edges) and let w : E(G) → [0, +∞)
Received 22 June 2020 be a weight function on the edge set of G. We consider the ratio between the maximum
Received in revised form 8 May 2021 weight of a perfect matching of G and the maximum weight of a matching of G. The
Accepted 10 May 2021
parameter η(G), introduced by Brazil & al. in Brazil et al. (2016), is defined as the
Available online 29 May 2021
minimum of such a ratio among all nonnegative edge weight assignments of G. In the
Keywords: present paper, we propose a way to compute a lower bound for the parameter η(G),
Perfect matching and we use it to prove that for every rational number q in the interval [0, 1] there
Maximal matching exists a graph G such that η(G) = q. Moreover, we further use the same method, in
Cubic graph combination with some new arguments, to establish the value of η for Prism graphs
and Möbius Ladders. Finally, we improve known results for Blanuša Snarks B1 and B2 by
determining the exact value of η(B1 ) and η(B2 ).
© 2021 Elsevier B.V. All rights reserved.

1. Introduction

In this note we consider the minimum ratio between the maximum weight of a perfect matching and the maximum
weight of a matching that can be achieved in a finite simple graph (i.e. a graph without loops and multiple edges). This
parameter, introduced by Brazil et al. in [2] and denoted by η, is well defined for each graph that admits a perfect matching.
More precisely,
maxP w (P)
η(G) = min
w maxM w (M)
where w : E(G) → [0, +∞) is a weight function on the edge-set of G, M is a matching of G and P is a perfect matching
of G. Let us recall that a matching of G is a set of independent edges and a matching is perfect if the number of its edges
is an half of the order of G.
The definition of η arises from an application in computer graphics as described in [2]. In particular it is a parameter
that aids the decision process on obtaining a quadrangulation of an object from its triangulation (see for instance [6]):
given a weight function on the face dual of the triangle mesh, a quadrangulation can be obtained with a perfect matching
of maximum weight, or with a two steps method that first finds a maximum weight matching, and then deals with the
unmatched triangles.
Clearly each perfect matching of a graph is a matching, then η assumes values in the interval [0, 1]. The authors of [2]
and [3] provided also a characterization of graphs which realize the extreme values of η, i.e. η = 0 and η = 1 (see also [7]),

∗ Corresponding author.
E-mail addresses: [Link]@[Link] (G. Mazzuoccolo), [Link]@[Link] (L. Mella).

[Link]
0166-218X/© 2021 Elsevier B.V. All rights reserved.
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

and some statements useful to establish lower and upper bounds for the parameter η. In [2] they focus on bridgeless cubic
graphs, as they naturally arise from the face dual of a triangle mesh and they prove the lower bound η ≥ 1/3 for each
graph in this class. Furthermore, they establish the value of η for some specific cubic graphs.
In order to prove that η(G) = q for a given graph G, it is usually not hard proving η(G) ≤ q, while, by the very definition
of η, it is often hard to show that η(G) ≥ q. In [3], the authors propose interesting methods to obtain lower bounds for
η(G). In Section 2, we continue the study in the same direction. Indeed, Proposition 2.1 gives a new method to obtain
a lower bound for η(G). Its proof can be viewed as a generalization of the proof for the lower bound η ≥ 1/3 for all
bridgeless cubic graphs G. At a first look, Proposition 2.1 could appear interesting only from a theoretical point of view,
since it needs a check for each maximal matching (i.e. a matching which is not properly contained in a larger matching)
of the graph G in order to obtain a lower bound. Moreover, its proof is straightforward. Nevertheless, we show along the
paper that we can use it in practice to obtain almost all results in the following sections. In Sections 3 and 4, we extend
the study of the parameter η in two directions: first of all, we present a way to construct a graph G such that η(G) = q for
any given rational value q ∈ [0, 1]. After that, we focus our attention on bridgeless cubic graphs: we establish the value
of η for the classes of Prism graphs and Möbius Ladders, and for the two Blanuša Snarks, thus improving results in [2].

2. A general lower bound for the parameter η

In this section we prove a tool to determine a lower bound of η(G) for an arbitrary finite simple graph G that we will
use in the following sections.

Proposition 2.1. Let G be a finite simple graph. If for every maximal matching M of G there exist (at most) t perfect matchings,
say P1 , . . . , Pt , of G such that every edge of M belongs to at least r of them, then η(G) ≥ rt .

Proof. Let w be an arbitrary nonnegative edge weight assignment of G and let M ′ be a matching of G. In order to prove
w (P ′ )
the assertion, we need to show that there exists a perfect matching P ′ such that w(M ′ ) is at least rt .
Take one of the maximal matching M of G such that M ⊆ M. By assumption, there exist P1 , . . . , Pt such that every edge
′

of M, and then of M ′ , belongs to at least r of them. Assume, without loss of generality, that w (P1 ) ≥ w (P2 ) ≥ · · · ≥ w (Pt ).
The following relations easily follow:
t
∑
r · w (M ′ ) ≤ r · w (M) ≤ w(Pi ) ≤ t · w (P1 ).
i=1

The assertion follows by setting P ′ = P1 . ■

In next sections, we show how we can apply this general result to some specific classes of graphs.

3. η(G) assumes each rational value in [0, 1]

This section is mainly devoted to prove that for each rational number m
n
in the interval [0, 1] there exists a graph G
such that η(G) = m n
.

3.1. Construction of the graph Bm,n

For every pair of integers 0 ≤ m ≤ n, with n ̸ = 0, consider the following sets:

Un1 = {u11 , . . . , u1n },
Vn1 = {v11 , . . . , vn1 },
and only if m < n also the sets:
Un2−m = {u21 , . . . , u2n−m },
Vn2−m = {v12 , . . . , vn2−m }.
We define the vertex-set and edge-set of the graph Bm,n as follows:
V (Bm,n ) = Un1 ∪ Vn1 ∪ Un2−m ∪ Vn2−m ,
E(Bm,n ) = X ∪ Y ∪ Z ;

where X = {u1i vj1 : i = 1, . . . , n and j = 1, . . . , n}, Y = {u1i u2j : i = 1, . . . , n and j = 1, . . . , n − m} and

Z = {vi1 vj2 : i = 1, . . . , n and j = 1, . . . , n − m} (see Fig. 1). Note that if m = n, then Bn,n is the complete bipartite
graph Kn,n having η = 1. For this reason, from now on, we limit our attention to the case m < n.
Note that the graph Bm,n can be described also as the complete bipartite graph K2n−m,2n−m with all the edges in an
induced subgraph Kn−m,n−m removed. Anyway, we stick with our description in order to simplify the presentation of
what follows.
20
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

Fig. 1. The graph B2,5 .

Lemma 3.1. Let P be a perfect matching of Bm,n . Then, |P ∩ X | = m.

Proof. Every vertex in Un2−m (Vn2−m ) is matched by P with a vertex in Un1 (Vn1 ), that is |P ∩ Y | = |P ∩ Z | = n − m. Hence,
there are exactly n − (n − m) = m vertices of Un1 matched with vertices of Vn1 , that is |P ∩ X | = m. ■

Lemma 3.2. A matching M of Bm,n can be extended to a perfect matching P if and only if |M ∩ X | ≤ m.

Proof. Assume that M can be extended to a perfect matching P. Then, by Lemma 3.1, |M ∩ X | ≤ |P ∩ X | = m. In order
to prove the converse, let M be a matching such that |M ∩ X | = k ≤ m, we need to show that M can be extended to a
perfect matching P. Observe that there exist at least m − k vertices of Un1 and at least m − k vertices of Vn1 unmatched in
M. Hence, we can extend M to a matching M ′ by arbitrarily choosing m − k edges of X with both ends unmatched in M.
Then, M ′ is a matching of Bm,n with exactly m edges in X . By removing all ends of the m edges in M ′ ∩ X and all edges of X ,
we remain with a subgraph of Bm,n which consists of two disjoint copies of the complete bipartite graph Kn−m,n−m : a copy
with edges in Y and the other with edges in Z . Every matching of a regular complete bipartite graph can be extended to a
perfect matching, then both M ′ ∩ Y and M ′ ∩ Z can be extended to a perfect matching of Kn−m,n−m . It is easy to check that
the union of such 2(n − m) edges and the m edges in M ′ ∩ X form a perfect matching P of Bm,n which contains M. ■

Theorem 3.3. For every positive integers 0 ≤ m < n, η(Bm,n ) = m

n
.

Proof. First we prove η(Bm,n ) ≤ m/n. Consider the edge weight function w such that w (u1i vi1 ) = 1, ∀i = 1, . . . , n, and
w(e) = 0 otherwise. By Lemma 3.1, each perfect matching P of Bm,n can contain at most m edges of X , then w(P) ≤ m for
every perfect matching, while there exists a matching M such that w (M) = n. It follows η(Bn,m ) ≤ m n
.
Now, we prove η(Bm,n ) ≥ m/n. By Proposition 2.1, we need to show that for every maximal matching M of Bm,n there
exist at most n perfect matchings which cover every edge of M at least m times. Set M ∩ X = {e1 , . . . , es }, with m ≤ s ≤ n
since M is maximal. Hence, the following holds:
|M | = |M ∩ X | + |M ∩ Y | + |M ∩ Z | = s + (n − s) + (n − s) = 2n − s.
Note that if s = m, then M itself is a perfect matching of G and by considering m copies of M we cover each edge
of M exactly m times with at most n perfect matchings. Hence, we can assume s > m. Consider for each 1 ≤ i ≤ s, the
m-subset of M:
Mi = {ei , ei+1 , . . . , ei+m−1 },
where operations in the indexing sets are taken modulo s. Since |Mi | = m for each i = 1, . . . , s, by Lemma 3.2, Mi can
be extended to a perfect matching Pi of Bm,n . Moreover, it can be easily checked that we can select Pi in such a way that
Mi ∪ (M ∩ Y ) ∪ (M ∩ Z ) ⊆ Pi . The set of s perfect matchings P1 , . . . , Ps cover each edge of M ∩ X exactly m times. Since
s ≤ n, η(Bm,n ) ≥ m/n by Proposition 2.1. The assertion follows. ■

4. Bridgeless cubic graphs

Bridgeless cubic graphs are a particular class of graphs which arises naturally from the dual of a triangulation. This
class has been subject of study for a long time in graph theory, and some classical results can be used in this context.
21
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

Fig. 2. Prism graph L10 and Möbius ladder M10 (two representations).

Let us mention, among others, Petersen’s Theorem [5] which guarantees the existence of a perfect matching. In [2], the
Perfect Matching Polytope characterization of Edmonds [4] is used to prove the following theorem.

Theorem 4.1 ([2]). If G is a cubic bridgeless graph, then η(G) ≥ 1/3.

The exact value of η for some cubic graphs of small order is reported in the same paper: η(PG) = 31 for the Petersen
graph PG, η(K3,3 ) = 1 and η(Q ) = 32 for the cube graph Q . Moreover, in the same paper the authors furnish upper bounds
of η for the two Blanuša snarks B1 and B2 of order 18 (see Section 4.2) .
In this section we determine the exact value of η for two infinite families of cubic graphs, Prisms and Möbius ladders,
and for the two snarks B1 and B2 .

4.1. Prisms and Möbius ladders

The Prism graph L2n of order 2n, for each n ≥ 3, is the cartesian product of a cycle graph Cn with a copy of K2 . The
result of this product can be represented as two copies of a cycle Cn , called inner and outer cycle, joined by n edges that
we will call spokes. We will denote by u0 , . . . , un−1 the vertices of the outer cycle and by v0 , . . . , vn−1 the vertices of the
inner cycle. The edge-set of L2n is given by
E(L2n ) = {ui ui+1 : i = 0, . . . , n − 1} ∪ {vi vi+1 : i = 0, . . . , n − 1} ∪ {ui vi : i = 0, . . . , n − 1},
where lower indices are all taken modulo n (see left side of Fig. 2).
A Möbius ladder M2n of order 2n is a graph obtained from L2n by replacing edges u0 un−1 and v0 vn−1 by the edges u0 vn−1
and v0 un−1 (see center of Fig. 2).
An alternative representation of M2n is obtained by considering the Hamiltonian cycle u0 u1 . . . un−1 v0 v1 . . . vn−1 u0 and
all spokes ui vi , for i = 0, . . . , n − 1 (see rightmost part of Fig. 2).
For both Prism graphs and Möbius ladders, we will denote the set of spokes by S. For a given spoke e = ui vi , we denote
by e− (e+ ) the spoke ui−1 vi−1 (ui+1 vi+1 ), where indices are taken modulo n. Moreover, we denote by ∂ − (e) the set of the
two edges having one end in {ui−1 , vi−1 } and the other end in {ui , vi }. Analogously, we denote by ∂ + (e) the set of the two
edges having one end in {ui , vi } and the other end in {ui+1 , vi+1 }. In particular, note that if e is the spoke u0 v0 (un−1 vn−1 )
of M2n , then ∂ − (e) (∂ + (e)) is the set of edges {un−1 v0 , vn−1 u0 }.

4.1.1. Lower bounds for η(L2n ) and η(M2n )

We use Proposition 2.1 to obtain lower bounds for η(L2n ) and η(M2n ). First of all, we prove the following lemmas.

Lemma 4.2. Let M be a maximal matching of L2n . Then, there exist two perfect matchings P1 and P2 of L2n such that M ⊆ P1 ∪P2 .

Proof. Let M be a maximal matching. We prove that in all cases there exists either a perfect matching P containing M or
an even 2-factor F containing M. In the former case we take P1 = P (and an arbitrary P2 ), in the latter case we can write
the edge-set of F as union of two disjoint perfect matchings P1 and P2 .
We distinguish two cases according to the parity of |M ∩ S | = h. Note that if h = n, then M is a perfect matching of
L2n and then the assertion follows by taking P = M. Hence, from now on, we can assume h < n.
Case h = 2k:
If h = 0 and n even, then the complement of S is an even 2-factor F containing M. If h = 0 and n odd, then there exists
a spoke e such that ∂ − (e) ∩ M is empty: we obtain an even 2-factor F (indeed an Hamiltonian cycle) containing M by
removing from G the two edges in ∂ − (e) and all spokes except to e and e− . Hence, we can assume h > 0. Let (e1 , . . . , e2k )
22
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

be the ordered list of elements in M ∩ S, where, without loss of generality, we can assume e1 = u0 v0 and we use the
clockwise order of spokes in a representation of L2n as in Fig. 2. We construct the required even 2-factor F in the following
way: remove from L2n all edges belonging to
∂ − (e1 ) ∪ ∂ + (e2 ) ∪ ∂ − (e3 ) ∪ · · · ∪ ∂ + (e2k );
note that this set is a matching of L2n since M is maximal, and we do not remove any edge of M since we remove only
edges which are incident to an edge of M. Now, we further remove all spokes which are not incident to one of the edges
already removed in the first step. Note that we do not remove any edge of M also in this step. The remaining edges induce
an even 2-factor of L2n which contains M.
Case h = 2k + 1:
As in the previous case, let (e1 , . . . , e2k+1 ) be the ordered list of elements in M ∩ S, where without loss of generality
we can assume e1 = u0 v0 and, since h < n, eh ̸ = un−1 vn−1 . Moreover, note that we also have eh ̸ = un−2 vn−2 since M is
maximal (by maximality, for every spoke e not in M, we cannot have that both e− and e+ belong to M). We construct an
even 2-factor F containing M in the following way: remove from L2n all edges belonging to
∂ − (e1 ) ∪ ∂ + (e2 ) ∪ ∂ − (e3 ) ∪ · · · ∪ ∂ + (e2k ) ∪ ∂ − (e2k+1 );
note that this set is a matching of L2n since M is maximal. Now, we further remove all spokes which are not incident
to one of the edges already removed. Note that we do not remove any edge of M also in this step. The remaining edges
induce an even 2-factor of L2n which contains M. ■

We omit the proof of the following lemma since it works exactly as the proof of Lemma 4.2 with some technical
variations which take care of the small difference between L2n and M2n .

Lemma 4.3. Let M be a maximal matching of M2n . Then, there exist two perfect matchings P1 and P2 of M2n such that
M ⊆ P1 ∪ P2 .

Corollary 4.4. For every n ≥ 3, the relations η(L2n ) ≥ 1

2
and η(M2n ) ≥ 1
2
hold.

Proof. The assertion follows by Lemmas 4.2, 4.3 and Proposition 2.1 with r = 1 and t = 2. ■

4.1.2. Upper bounds for η(L2n ) and η(M2n )

Here, we consider the easier task of establishing upper bounds for η(L2n ) and η(M2n ). In view of previous section and
the following lemma, we will summarize the value of η for all possible Prisms and Möbius ladders in Theorem 4.8.

Lemma 4.5. For every positive integer k, the relations η(L4k+2 ) ≤ 1

2
and η(M4k+4 ) ≤ 1
2
hold.

Proof. Consider the weight function w such that w (u0 u1 ) = w (v1 v2 ) = 1 and w (e) = 0 for any other edge e. Every perfect
matching can contain only one of these two independent edges, then the assertion follows. ■

Lemma 4.6. For every positive integer k ≥ 3, the relations η(L4k ) ≤ 1

2
and η(M4k+2 ) ≤ 1
2
hold.

Proof. Consider the weight function w such that w (u0 u1 ) = w (v1 v2 ) = w (u3 u4 ) = w (v4 v5 ) = 1 and w (e) = 0 for any
other edge e. Every perfect matching can contain only two of these four independent edges, then the assertion follows. ■

In view of previous two lemmas, only the small cases L8 , M6 and M10 remain open. Notice that L8 is the cube graph Q ,
while M6 is the complete bipartite graph K3,3 : for both of them the value of η is known. Hence, the only remaining case
is M10 that we consider in the following proposition.

Proposition 4.7. η(M10 ) = 2

3
.

Proof. We can easily prove η(M10 ) ≤ 23 by considering the weight which assigns 1 to an edge if it belongs to
{u1 u2 , v0 v1 , v3 v4 } and 0 otherwise. It is clear that every perfect matching of M10 can contain at most two of the three
edges u1 u2 , v0 v1 , v3 v4 and then η(M10 ) ≤ 32 holds.
Now, we prove η(M10 ) ≥ 32 by using Proposition 2.1. We need to prove that for every maximal matching M of M10
there exist three perfect matchings P1 , P2 , P3 covering each edge of M at least twice. If M is a perfect matching, then the
assertion trivially follows by taking P1 = P2 = P3 = M. There is no maximal matching of M10 of size less than 4 (direct
easy check). Let M be a maximal matching of M10 of size 4. Let x and y be the two unmatched vertices in M10 : we can
assume without loss of generality that x = u0 because of symmetry of M10 . Note that M10 is a bipartite graph, then y is
a vertex in the opposite bipartite class with respect to u0 , that is y ∈ {u1 , u3 , v0 , v2 , v4 }. Moreover, y cannot belong to
{u1 , v0 , v4 }, since that vertices are adjacent to u0 and M is maximal. Hence, either y = u3 or y = v2 : again by symmetry
23
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

Fig. 3. For every maximal matching of M10 , there exist three perfect matchings covering each edge of the matching at least twice.

of M10 we can assume without loss of generality that y = u3 . There exist exactly three maximal matching of M10 having
size 4 and with u0 and u3 unmatched, represented in Fig. 3.
For each of them we show in Fig. 3 three perfect matchings containing each edge of the matching at least twice. The
assertion follows. ■

We are in position to summarize the content of this section by giving the value of η for all Prisms and Möbius Ladders.

Theorem 4.8. For every n ≥ 3, the following hold:

{
2
if n = 4
η(L2n ) = 3
1
2
otherwise,
⎧
⎨1
⎪ if n = 3
η(M2n ) = 2
3
if n = 5
⎪
⎩ 1
2
otherwise.

4.2. Blanuša Snarks

A dot product of two cubic graphs G and H, denoted by G · H is defined as follows. Remove a pair of adjacent vertices
u and v in G and a pair of two independent edges ab and cd in H; denote by u1 , u2 and v1 , v2 the other neighbors of u
and v in G, respectively. Finally, join the vertices {u1 , u2 } to {a, b} with two new edges, and {v1 , v2 } to {c , d} with other
two new edges. Notice that in general several different dot products are possible according to the connection selected.
Note also that switching the order of u and v we can obtain different dot products.
The Blanuša Snarks are two classical snarks (see [1]) both obtained as dot product of two copies of the Petersen graph
PG. It is not hard to see that due to the symmetry of the Petersen graph there exist only two different possible dot products
PG · PG: indeed, the choice of the two adjacent vertices in one copy of PG is not relevant, and only the distance between
the two independent edges in the other copy of PG matters (see Fig. 4).
Brazil et al. [2] established the following upper bounds for η of both Blanuša Snarks:

Proposition 4.9 ([2]). Let B1 be the first Blanuša Snark. Then, η(B1 ) ≤ 2/5.

Proposition 4.10 ([2]). Let B2 be the second Blanuša Snark. Then, η(B2 ) ≤ 1/2.

Firstly, we determine the exact value of η(B1 ) by showing a weight function that allow us to use the lower bound of
Theorem 4.1. After that we determine η(B2 ) by checking the condition in Proposition 2.1 with a computer search.

24
G. Mazzuoccolo and L. Mella Discrete Applied Mathematics 301 (2021) 19–25

Fig. 4. Constructions of the two Blanuša snarks.

Proposition 4.11. Let B1 be the first Blanuša Snark. Then, η(B1 ) = 1/3.

Proof. Let M be the matching of B1 depicted in bold in the left part of Fig. 4, and define a weight function w such that
w(e) = 1 if and only if e belongs to M. It now can be easily checked that a perfect matching can contain at most one of
the edges in M, thus obtaining η(B1 ) ≤ 1/3. Therefore, since B1 is a bridgeless cubic graph, by Theorem 4.1 the assertion
follows. ■
Now, we move our attention on B2 . Let M be the matching of B2 depicted in bold in the right part of Fig. 4 and define a
weight function w such that w (e) = 1 if and only if e belongs to M. A direct check shows that every perfect matchings of
B2 can contain at most two edges of M, thus obtaining η(B2 ) ≤ 2/5. Now, by using a computer procedure, we determine
all maximal matching of B2 which are not perfect matching. There are 688 matchings of size 8, 898 matchings of size
7 and 50 matchings of size 6. Then, we check that for each of them there exist at most 5 perfect matchings of B2 such
that every edge of the matching belongs to at least 2 of them, thus by Proposition 2.1 we obtain η(B2 ) ≥ 2/5, and the
following proposition follows.

Proposition 4.12. Let B2 be the second Blanuša Snark. Then, η(B2 ) = 2/5.

5. Final remarks

In the present paper, we propose a new way to compute the lower bound for the parameter η(G), see Proposition 2.1.
We use it to prove that for every rational number m n
in the interval [0, 1] there exists a graph G such that η(G) = mn
, see
Theorem 3.3. Moreover, we use it in Section 4.1 to establish the value of η for Prism graphs and Möbius Ladders, and in
Section 4.2 to improve some known results for two classical snarks.
As far as we know, there is no example of a graph G such that η(G) is strictly larger than the best lower bound provable
by using Proposition 2.1. In other words, we wonder if for all fractions rt ≤ η(G) and for every (maximal) matching of G,
there exist t perfect matchings covering each edge of M at least r times. An affirmative answer would imply an equivalent
definition for the parameter η and, as a by-product, we would obtain that η(G) is always a rational number.

References

[1] D. Blanuša, Problem cetiriju boja, Glas. Mat. Fiz. Astr. Ser. II 1 (1946) 31–42.
[2] E.V. Brazil, G.D. da Fonseca, C. de Figueiredo, D. Sasaki, The cost of perfection for matchings in graphs, Discrete Appl. Math. 210 (2016) 112–122.
[3] G.D. da Fonseca, B. Ries, D. Sasaki, On the ratio between maximum weight perfect matchings and maximum weight matchings in grids, Discrete
Appl. Math. 207 (2016) 45–55.
[4] J. Edmonds, Maximum matching and a polyhedron with 0, 1–vertices, J. Res. Natl. Bur. Stand. (U.S.) Ser. B 69 (1965) 55–56.
[5] J. Petersen, Die theorie der regulären graphs, Acta Math. 15 (1891) 193–220.
[6] S. Ramaswami, P. Ramos, G. Toussaint, Converting triangulations to quadrangulations, Comput. Geom. 9 (1998) 257–276.
[7] D.P. Summer, Randomly matchable graphs, J. Graph Theory 3 (1979) 183–186.

25