Proof. See 1. It is elementary to verify that all of the theorem’s statements hold, except for the last one. But this follows directly from Mader’s result stating that every matchable 2-connected graph with minimum degree at least 3 except \(K_4\) has at least four perfect matchings [5].

 ◻

Proof. Assume there is an edge \(e = vw \in Y\) in a perfect matching \(M\) of \(G + Y\). Without loss of generality, \(v,w \in A\). We have \(|A| = |B|\). For each \(b \in B\) we have an edge \(e_b \in M\) such that \(b\) is incident with \(e_b\); moreover, \(|M| \ge |B|\). Since \(e\) is also in \(M\) but not incident with any \(b \in B\), we have \(|M| > \frac{|V(G)|}{2}\), a contradiction. ◻

Proof. Put \(k := |V(H)|\). Consider \(C_{2k} \Box K_2 =: G\), a cubic planar 3-connected graph of order \(n = 4k\). We have \(\Phi(G) \ge 2^{n/4}\). We embed this graph such that we have an exterior \(2k\)-gon \(P\), forming the boundary cycle of the infinite face. In \(P\), a bipartite graph, we consider every second vertex, and add edges until \(H\) is obtained. As \(G\) is 3-connected, this graph must also be 3-connected; as \(G\) is planar and \(H\) is outerplanar, this graph must also be planar. By 2, every edge of \(H\) is inadmissible. ◻

Proof. Since \(L\) and \(H\) are matchable, so is \(G\). Let \(M\) be a perfect matching in \(G\). Let \(T := M \cap S\). We have \(|T|\) even as \(H\) and \(L\) have even order. Suppose \(|T| > 0\). Let \(X\subseteq D\) be the set of vertices in \(H\) incident with an edge in \(T\). Then \(H - X\) has a perfect matching \(N\). Let \(H'\) be the graph obtained from \(H\) by adding every missing edge between distinct vertices of \(X\), so that the vertices in \(X\) induce a clique in \(H\). Then \(N \cup Q\), with \(Q\) a perfect matching of \(H'[X]\), is a perfect matching of \(H'\), contradicting the assumption that \(D\) is inadmissible. The very last statement is due to the Fact stated just before the lemma. ◻

Proof. We will give an infinite family of graphs for each case. The infinite families for (i), (iii), and (iv) make use of the planar bipartite graph \(H\) as drawn in 2. By 2 any subset of edges from \(\{ t_1t_2, t_1t_3, t_2t_3\}\) added to \(H\) is inadmissible.

Consider, for an even positive integer \(m\), the ladder graph \(L_{m} := P_{m/2} \Box K_2\) of order \(m\ge2\).

Case 1. \(n_0= 10\), \(c=12\), \(G\) has four vertices of degree \(4\) and \(n-4\) vertices of degree \(3\).

First, suppose that \(n=10\). Take \(H\) and add the two edges \(t_1t_2\) and \(t_1t_3\). The obtained graph \(G_{1,10}\) still has 12 perfect matchings since \(t_1t_2\) and \(t_1t_3\) are inadmissible. Moreover, \(G_{1,10}\) is 3-connected, planar, has 4 vertices of degree 4 and \(n-4=6\) vertices of degree 3.⁷

Now, suppose that \(n=12\). Take the disjoint union of \(H\) with \(K_2\) with \(V(K_2) = \{x,y\}\), and add the edges \(t_1x, t_1y, t_2x, t_3y\). The obtained graph \(G_{1,12}\) is 3-connected, planar, has four vertices of degree \(4\) and \(n-4=8\) vertices of degree \(3\). Furthermore, \(\Phi(G_{1,12})=12\) since \(\Phi(K_2)=1\) and \(xy\) is the only added admissible edge. All other added edges are inadmissible due to the inadmissibility of \(\{t_1,t_2,t_3\}\), by 3.

Lastly, suppose that \(n\ge14\) and \(n\) is even. In \(L_m\), let \(z_1,z_2\) be the two adjacent vertices of degree 2 on one end of the ladder and \(z_3,z_4\) the ones on the other end. For \(m=2\), the pairs coincide, so \(z_1=z_3\) and \(z_2=z_4\). We define the graph \(L_m^*\) for \(m\ge4\) as the ladder graph \(L_{m-2}\) where we add two vertices \(x\), \(y\) and add three edges \(xz_1\), \(yz_3\), \(yz_4\). Note that \(\Phi(L_m^*)=1\). Consider now \(H\) to be embedded as shown in 2. Take \(G_{1,n}\) as \(H\) where we place \(L_{n-10}^*\) in the face whose boundary cycle contains \(t_1,t_2\) and \(t_3\), and connect it to \(H\) with the edges \(t_1z_2\), \(t_1x\), \(t_2x\), \(t_3y\). The graph \(G_{1,n}\), depicted in 2, is a 3-connected (this can be verified by a routine argument using Menger’s Theorem) planar \(n\)-vertex graph that has four vertices of degree \(4\), \(n-4\) vertices of degree \(3\), and has \(\Phi(H) \cdot \Phi(L_{n-10}^*)=12\) perfect matchings by 3.

Case 2. \(n_0= 14\), \(c=18\), \(G\) has two vertices of degree \(5\) and \(n-2\) vertices of degree \(3\).

The proof is analogous to the one of Case 1, except that we replace \(H\) by \(I\) from 3, which leads to a graph with 18 perfect matchings (instead of 12), two vertices of degree 5 and \(n-2\) vertices of degree \(3\).

Case 3. \(n_0= 10\), \(c=12\) and \(G\) is a triangulation.

Triangulate the graph \(H\) by adding edges between the vertices of the red partite set. This triangulation \(J\) is a planar 3-connected 10-vertex graph. All the added edges are inadmissible by 2, hence, \(\Phi(J)=\Phi(H)=12\), which solves this case for \(n=10\).

Suppose now that \(n\ge12\) and \(n\) is even. Consider the triangulation \(J\) with the inadmissible set \(\{t_1, t_2, t_3\}\). Add a \(K_2\) with \(V(K_2) = \{x,y\}\) to \(J\) and the edges \(t_1x, t_1y, t_2x, t_2y, t_3y\) (which is the same for Case 1 where \(n=12\), but we added the edge \(t_2y\) as well). The obtained graph \(G_{3,12}\) is a 3-connected planar triangulation and has 12 perfect matchings since \(xy\) is the only added admissible edge. Now, \(\{t_1, t_2, x\}\) is an inadmissible set and we can recursively apply the same operation of adding \(K_2\) while maintaining the same number of perfect matchings. So, Case 3 holds for any even \(n\ge 12\).
Case 4. \(n_0= 22\), \(c=144\), \(G\) is bipartite, has eight vertices of degree \(4\) and \(n-8\) vertices of degree \(3\).

Consider two copies \(H^{(1)}, H^{(2)}\) of the graph \(H\), where a vertex \(v\) from \(H\) is denoted as \(v^{(1)}\) in \(H^{(1)}\) and \(v^{(2)}\) in \(H^{(2)}\).

Suppose \(n=22\).⁸ Consider the graph \(G_{4,22}\) consisting of \(H^{(1)}, H^{(2)}\), a \(K_2\) with \(V(K_2) = \{x^{(1)},x^{(2)}\}\), and the edges \(t_1^{(1)}t_1^{(2)}, t_1^{(1)}x^{(1)}, t_1^{(2)}x^{(2)}, t_3^{(1)}x^{(1)}, t_3^{(2)}x^{(2)}, t_2^{(1)}t_2^{(2)}\). The graph \(G_{4,22}\), depicted in 5, is 3-connected, planar, bipartite, has eight vertices of degree 4 and \(n-8=14\) vertices of degree 3.

By 2 the set \(\{t_1^{(1)}, t_2^{(1)}, t_3^{(1)}\}\) is inadmissible in \(H^{(1)}\) and \(\{t_1^{(2)}, t_2^{(2)}, t_3^{(2)}\}\) is inadmissible in \(H^{(2)}\). Apply 3 with \(H = H^{(1)}\) and \(L = K_2\). When doing so, we add the edges \(t_3^{(1)} x^{(1)}\) and \(t_1^{(1)} x^{(1)}\). Let us call the resulting graph \(R\). We then apply 3 with \(H = H^{(2)}\) and \(L = R\). Thus, all added edges except \(x^{(1)}x^{(2)}\) are inadmissible. Since \(\Phi(H) = 12\) and \(\Phi(K_2) = 1\), we have \(\Phi(G_{4,22})= 144\).

Suppose \(n\ge24\) and \(n \equiv_4 0\), which stands for \(n = 0\) modulo 4. Consider the ladder graph \(L_{n-18}\) with \(z^{(1)}\) and \(z^{(2)}\) as two vertices of degree 2 in \(L_{n-18}\) which are at distance \(\frac{n-18}{2}\) (this is the diameter of \(L_{n-18}\)) from each other. Now, construct the graph from \(H^{(1)}, H^{(2)}\), and \(L_{n-18}\), where we identify \(z^{(1)}\) with \(t_1^{(1)}\) and \(z^{(2)}\) with \(t_1^{(2)}\). Additionally, add the three edges \(t_2^{(1)}y^{(1)},t_3^{(2)}y^{(2)}, t_3^{(1)}t_2^{(2)}\), where \(y^{(1)}\) and \(y^{(2)}\) are the degree 2 neighbours of \(z^{(1)}\) and \(z^{(2)}\) in \(L_{n-18}\), respectively. The resulting graph \(G_{4,n \equiv_4 0}\), depicted in 6, is 3-connected, planar, bipartite, has order \(n\) with \(n\ge24\) and \(n \equiv_4 0\), has 8 vertices of degree 4 and \(n-8\) vertices of degree 3.

We now prove that \(\Phi(G_{4,n \equiv_4 0}) = 144.\) Let \(L' := G_{4,n \equiv_4 0} - H^{(1)} - H^{(2)}\). First apply 3 with \(H = H^{(1)}\) and \(L = L'\); here \(D = \{ t_1^{(1)}, t_2^{(1)} \}\). We denote the resulting graph by \(H'\). We then apply 3 with \(H = H^{(2)}\) and \(L = H'\); here \(D = \{ t_1^{(2)}, t_2^{(2)}, t_3^{(2)} \}\). Since the induced subgraph \(G_{4,n \equiv_4 0}[V(L_{n-18})\setminus \{t_1^{(1)}, t_1^{(2)}\}]\), which is isomorphic to \(L'\), only has one perfect matching, it follows that \(\Phi(G_{4,n \equiv_4 0})=\Phi(H)^2=144\).

Suppose \(n\ge24\) and \(n \equiv_4 2\). Similar to the case \(n \equiv_4 0\), consider \(L_{n-20}\) with \(z^{(1)}\) and \(z^{(2)}\) as two vertices of degree 2 in \(L_{n-20}\) which are at distance \(\frac{n-20}{2}\). Consider the graph constructed from \(H^{(1)}, H^{(2)}\), and \(L_{n-20}\), where we identify \(z^{(1)}\) with \(t_1^{(1)}\) and \(z^{(2)}\) with \(t_1^{(2)}\). Take \(y^{(1)}\) and \(y^{(2)}\) as the degree 2 neighbours of \(z^{(1)}\) and \(z^{(2)}\) in \(L_{n-20}\), respectively. Take \(w^{(2)}\) as the degree 3 neighbour of \(z^{(2)}\) in \(L_{n-20}\). Delete the edge \(w^{(2)} t_1^{(2)}\). In contrast with the previous construction, we now add a \(K_2\) with \(V(K_2) = \{x^{(1)},x^{(2)}\}\), and also the edges \(t_2^{(1)}y^{(1)}, t_3^{(1)} x^{(1)}, t_1^{(2)} x^{(2)}, t_2^{(2)} w^{(2)}, t_3^{(2)} x^{(2)}, y^{(2)} x^{(1)}\). The resulting graph \(G_{4,n \equiv_4 2}\), depicted in 7, is 3-connected, planar, bipartite, has order \(n\) with \(n\ge24\) and \(n \equiv_4 2\), has 8 vertices of degree 4 and \(n-8\) vertices of degree 3.

We now prove that \(\Phi(G_{4,n \equiv_4 2}) = 144.\) Let \(L'' := G_{4,n \equiv_4 2} - H^{(1)} - H^{(2)}\). First apply 3 with \(H = H^{(1)}\) and \(L = L''\); here \(D = \{ t_1^{(1)}, t_2^{(1)}, t_3^{(1)} \}\). We denote the resulting graph by \(H''\). We then apply 3 with \(H = H^{(2)}\) and \(L = H''\); here \(D = \{ t_1^{(2)}, t_2^{(2)}, t_3^{(2)} \}\). Since \(L''\) only has one perfect matching, it follows that \(\Phi(G_{4,n \equiv_4 2})=144\).

Case 5. \(n_0= 24\), \(c=768\) and \(G\) has minimum degree \(4\) and \(G\) is a triangulation.

Consider \(R_4\) as a \(C_4\) with consecutive vertices \(z_1, z_2, z_3, z_4\) to which we add the edge \(z_2 z_4\). Consider \(R_m\) with even \(m\ge 6\) as the disjoint union of \(R_4\) and a path graph \(P_{m-4}\) with consecutive vertices \(p_1, \dots, p_{m-4}\) where we add the edge \(z_1 p_{m-4}\). Note that \(\Phi(R_m)=2\).

Suppose \(n\ge 24\) is even and take \(G_{5,n}\) as \(Q\) as drawn in 8. The graph \(Q\) can be obtained from the graph \(H\) in two steps. First, just like in Case 3, we triangulate \(H\) by adding edges between the vertices of the red partite set. We call the resulting graph \(J\). Second, we replace each vertex of the blue partite set by a triangle and triangulate the graph by adding two edges to each vertex of an added triangle. The obtained graph is \(Q\). By doing the replacement operation for exactly one blue vertex, the resulting graph has twice the number of perfect matchings of the original graph. Since there are five blue vertices in \(J\) and because \(\Phi(J)=12\), we thus have \(\Phi(Q)=12 \cdot 2^5=384\). Furthermore, each inadmissible set of three vertices in \(J\) stays inadmissible in \(Q\), in particular \(\{t_1,t_2,t_3\}\) stays inadmissible. Now, place \(R_{n-20}\) in the common face of vertices \(t_1,t_2,t_3\). Add the edge \(t_1 z_1\) in case \(n=24\) and \(t_1 p_1\) otherwise. In addition, add the edges \(x p_1, \dots, x p_{n-24}, x z_1, x y, x z_3\) for \(x \in \{t_2,t_3\}\) where \(y=z_2\) for \(x=t_2\) and \(y=z_4\) for \(x=t_3\). The obtained graph \(G_{5,n}\) is a planar triangulation with minimum degree 4.

By applying 3 with \(H=Q\), \(D=\{t_1,t_2,t_3\}\), and \(L=R_{n-20}\), we conclude that \(\Phi(G_{5,n})=\Phi(Q) \cdot \Phi(R_{n-20})=768\). ◻

Proof. Take an arbitrary edge \(e=uv\) in a planar 5-connected \(n\)-vertex graph \(G\), with \(n\) even. Consider the graph \(H = G-u-v\), which is 3-connected and 1-extendable since \(G\) is 2-extendable [8]. These two properties of \(H\) imply that \(|E(F(H))|=|E(H)|\ge \frac{3(n-2)}{2}\) and hence applying 1 on \(H\) gives \(\Phi(H) \ge\frac{n+6}{4}\). We can extend each perfect matching \(M\) of \(H\) to a perfect matching in \(G\) by adding the edge \(e\) to \(M\). Thus, \(e\) is contained in at least \(\frac{n+6}{4}\) perfect matchings. ◻

Proof. Consider the prism over a complete graph, that is: the Cartesian product \(\Pi_k := K_k \square K_2\). We denote by \(M\) the set of edges of \(\Pi_k\) not contained in one of the two copies of \(K_k\).

A perfect matching in \(\Pi_k\) uses some number \(i\) of edges in \(M\), \(0 \le i \le |M|\), such that the remaining number of vertices \(k-i\) in each \(K_k\) is even. Since the number of perfect matchings in a complete graph of order \(2j\) is \((2j-1)!!\), we have

\[\Phi(\Pi_k) = \sum_{j=0}^{\lfloor k/2\rfloor} \binom{k}{2j}\bigl((2j-1)!!\bigr)^2.\]

Put \(a_k := \Phi(\Pi_k)/k!\). By

\[(2j-1)!!=\frac{(2j)!}{2^j j!}\] we get \[a_k = \sum_{j=0}^{\lfloor k/2\rfloor} \frac{\binom{2j}{j}}{4^j\,(k-2j)!}.\]

We now show that \(\lim_{k\to\infty} a_k = 0.\) Let \[b_j:=\frac{\binom{2j}{j}}{4^j}.\]

We have \(0\le b_j\le 1\) for all \(j\), since \(\binom{2j}{j}\le 4^j\). Furthermore, it can be inferred from Stirling’s work that \(n! = \sqrt{2\pi n}\,(n/e)^n(1+O(\frac{1}{n}))\). This yields \[\binom{2j}{j} = \frac{(2j)!}{(j!)^2} \sim \frac{\sqrt{4\pi j}\,(2j/e)^{2j}}{(\sqrt{2\pi j}\,(j/e)^j)^2} = \frac{\sqrt{4\pi j}\,2^{2j} j^{2j}/e^{2j}}{2\pi j \cdot j^{2j}/e^{2j}} = \frac{4^j}{\sqrt{\pi j}}\] and \[\frac{\binom{2j}{j}}{4^j} = \frac{1}{\sqrt{\pi j}}\left(1 + O\!\left(\tfrac{1}{j}\right)\right).\] Hence, there is a constant \(C>0\) such that \[b_j\le \frac{C}{\sqrt{j+1}} \qquad\text{for all } j\ge 0.\] Now split the sum defining \(a_k\) into two parts: \[a_k = \sum_{j=0}^{\lfloor k/2\rfloor}\frac{b_j}{(k-2j)!} = \sum_{j=0}^{\lfloor k/4\rfloor}\frac{b_j}{(k-2j)!} \;+\; \sum_{j=\lfloor k/4\rfloor+1}^{\lfloor k/2\rfloor}\frac{b_j}{(k-2j)!}.\] Let us denote the first sum by \(S_1\) and the second sum by \(S_2\). For \(S_1\), we have \(k-2j\ge \lfloor k/2 \rfloor\), hence \[S_1 \le \sum_{j=0}^{\lfloor k/4\rfloor}\frac{1}{\lfloor k/2 \rfloor !} \le \frac{k/4+1}{\lfloor k/2\rfloor!}\xrightarrow[k\to\infty]{}0.\] For \(S_2\), we have \(j>\frac{k}{4}\), so \(j+1\ge \frac{k}{4}\), and therefore \[b_j\le \frac{C}{\sqrt{j+1}}\le \frac{2C}{\sqrt{k}}.\] Thus \[S_2 \le \frac{2C}{\sqrt{k}}\sum_{j=0}^{\lfloor k/2\rfloor}\frac{1}{(k-2j)!} \le \frac{2C}{\sqrt{k}}\sum_{m=0}^{\infty}\frac{1}{m!} = \frac{2Ce}{\sqrt{k}} \xrightarrow[k\to\infty]{}0.\] ◻