一类管状富勒烯图的完美匹配数

The Number of Perfect Matching of Tubular Fullerene Graphs

摘要: 富勒烯图是3-连通3-正则平面图，并且恰好具有12个五边形面，其余的面都是六边形面。本文研究的富勒烯图是由六个同心的六边形层组成，两端都由一个六边形以及与这个六边形相邻的六个五边形面构成的顶盖封口。我们把该类富勒烯图称为管状富勒烯图。完美匹配计数在量子化学领域以及统计物理领域中具有广泛的应用，并且已被证实完美匹配计数问题是一个NP-难的问题。本文主要通过划分、求和以及嵌套递推的方式求出管状富勒烯图的完美匹配数。

Abstract: A fullerene graph is 3-connected cubic planar graph, and has exactly 12 pentagonal faces, the rest of which are hexagonal faces. The fullerene graph studied in this paper is composed of six concentric layers of hexagons, capped on each end by a cap formed by a hexagon and six pentagonal faces adjacent to the hexagon. This kind of fullerene graphs is called tubular fullerene graphs. The problem of counting the number of perfect matching is widely used in the field of quantum chemistry and statistical physics, and it has been proved that the problem of counting the number of perfect matching is NP-hard. In this paper, the number of perfect matching of tubular fullerene graphs is obtained by means of partition, summation and nested recursion.

1. 引言

图的完美匹配计数问题是一个具有很强应用背景的问题，主要涉及到量子化学和统计物理领域。在量子化学领域，完美匹配被称为Kekulé结构，而Kekulé结构是描述分子稳定性的一个重要指标；在统计物理领域，完美匹配则被称为Dimer构型，而Dimer构型是描述在格点模型中粒子分布的一种方式[1] [2]。因此，研究完美匹配的计数问题不仅有助于理解这些领域的复杂现象，还可能为解决实际问题提供理论依据和计算方法。同时，对图的完美匹配计数问题的研究不仅在实践中具有重要意义，而且在图论的其它领域也有广泛的应用，如匹配算法、网络流等领域[3] [4]。

然而，Valiant证明了即使是二部图的完美匹配计数问题也是NP-难的[5]。科学家Kasteleyn首次提出运用图的Pfaffian定向来研究图的完美匹配计数问题[6]。并指出如果图G有一个Pfaffian定向，那么其完美匹配数就能在多项式时间内算出。Kasteleyn的一个经典定理就是证明了所有的平面图都是Pfaffian的[7]。利用Pfaffian定向的方法，Kasteleyn得到了平面四角格子和环面格子图完美匹配数的精确表达式[6]。Little推广了Kasteleyn的结果并且证明如果一个图G不包含$K_{3,3}$ 的细分，则G有一个Pfaffian定向[8]。尽管有许多等价条件证明图Pfaffian定向的存在性[8] [9]，但没有多项式时间算法来检查图G的一个给定定向是否为Pfaffian定向。Lu和Wu构造了能嵌入到莫比乌斯带，Klein瓶上的四方形网格的一个Pfaffian定向，并给出了这些图的完美匹配数的显式表达式[10]。运用Pfaffian方法还可以简化某些图类的完美匹配数的计算[11]-[13]。Yan和Zhang利用圈C₄，路P₄与树的乘积图的Pfaffian性得到了一些图的完美匹配数的显式表达式[14]。Propp介绍了许多关于图的完美匹配计数问题的应用背景及其研究进展[15]。更多相关的内容可以参考文献[16]-[18]。

除了利用Pfaffian定向来计算图的完美匹配数外，还可以利用图自身的特殊结构求其匹配数。比如在1985年，张福基等人研究了树状多六边形(简写为TPH)的完美匹配数，得出TPH图的完美匹配计数相当于树状苯型渺位稠合多环芳香体系的Kekulé结构计数[19]。在1997年，张和平等人研究四角系统完美匹配数，证明非基本四角系统的完美匹配数等于一些基本子四角系统完美匹配数的乘积[20]。在2005年，林泓等人研究了若干四角系统的完美匹配计数，利用组合递推法给出了几类四角系统的完美匹配数的显式表达式[21]。在2014年，唐保祥等人利用划分、求和，再嵌套递推的方法给出了几类特殊图完美匹配数的显式表达式[22]。马京成等人研究了3-正则Halin图的完美匹配计数问题，给出了3-正则Halin图的完美匹配数的一个递推公式，同时，他们还给出了两类特殊的Halin图的完美匹配数下界的计算公式[23]。2023年，叶银珠等人利用Dong等人给出的偶数条边树的线图完美匹配数的表达式，得到一类繁星树线图的完美匹配数的最大值和最小值[24] [25]。更多关于完美匹配数的计算问题，请参考文献[26]-[28]。

富勒烯是一种完全由碳组成的中空分子，形状有球形，椭球形，柱形和管状。而管状富勒烯图就是两端有封口的单壁碳纳米管或巴基管[29]。富勒烯由于其特殊的机械、物理、化学性能在工程材料、催化、吸附分离、储能器件电极材料等诸多领域得到了广泛应用[30]。在1998年，Došlić研究了富勒烯图的完美匹配数的下界，证明n个顶点的富勒烯图至少有$n/2+1$ 个完美匹配[31]。在2001年，张和平等人改进了Došlić等人的结果，得出n个顶点的富勒烯图的完美匹配数的下界为$\lceil 3\left(n+2\right)/4\rceil$ [32]。在2009年，Kardoš等人利用四色定理得到在一般情况下的具有n个顶点且不包含非平凡5-边割的富勒烯图至少有$2^{\left(n-380\right)/61}$ 个完美匹配[33]。在2012年，鞠阳研究了富勒烯邻接矩阵积和式的界估计结果及其与富勒烯完美匹配数之间的定量关系，得出富勒烯完美匹配数的一个新的下界估计：$2^{n/14.46-11/6}$ [34]。在2016年，王芳研究了富勒烯图完美匹配数和共振型个数的比较，得出对所有的富勒烯图，富勒烯图中共振型个数严格小于完美匹配个数[35]。后来在2020年，钱进研究了富勒烯的完美匹配数的下界及其稳定性，得出比之前更优的富勒烯的完美匹配数的下界估计[36]。Lovász和Plummer曾经提出一个关于图的完美匹配计数问题的一个猜想：任意2-边连通3-正则图都有指数多个完美匹配[37]。Esperet等人在2011年证明了n个顶点的2-边连通3-正则图至少有$2^{n/3656}$ 个完美匹配[38]，从而解决了Lovász和Plummer提出的猜想。

本文研究的管状富勒烯图是由六个同心的六边形层组成，两端都由一个六边形以及与这个六边形相邻的六个五边形面构成的顶盖封口，记作F。本文证明了以下结果，验证了Lovász和Plummer猜想的正确性。

定理1 对于管状富勒烯图F，F的完美匹配数为$\left[2+{\left(2+\sqrt{3}\right)}^{\frac{s-12}{12}}+{\left(2-\sqrt{3}\right)}^{\frac{s-12}{12}}\right]\left(2^{\frac{s+12}{12}}+1\right)$ (其中s为F的顶点数)。

本文的结构安排如下：第一部分，介绍了完美匹配计数问题的研究背景，研究进展，富勒烯的完美匹配数的研究进展，以及本文的主要结论。第二部分为准备工作，给出本文需要用的一些符号和概念。第三部分，利用图的结构和递推公式证明本文主要结论。

2. 准备工作

设$V\left(G\right)$ 和$E\left(G\right)$ 分别是图G的顶点集和边集，分别用$\left|V\left(G\right)\right|$ 和$\left|E\left(G\right)\right|$ 表示图G的顶点集和边集的个数。设$\left|V\left(G\right)\right|=n$ ，$\left|E\left(G\right)\right|=m$ ，如果$e\in E\left(G\right)$ ，通过从G中删除e而保持顶点和其余边不变来获得一个$m-1$ 条边的图，得到的图用$G\backslash e$ 表示。类似地，如果$v\in V\left(G\right)$ ，通过从G中删除顶点v以及所有与v关联的边来得到一个$n-1$ 个顶点的图，得到的图用$G-v$ 表示。对$H\subseteq V\left(G\right)\cup E\left(G\right)$ ，设$G-H$ 是通过从G中删除在H中的元素而获得的子图。

图G的途径是指一个点边交替序列$W=v_0{e}_1{v}_1\cdots e_i{v}_i\cdots e_{k-1}{v}_{k-1}{e}_k{v}_k$ ，其中$e_i=v_{i-1}{v}_i$ 是图的一条边($1\le i\le k$ )，称W是从$v_0$ 到$v_k$ 的一条途径，或一条$\left(v_0,v_k\right)$ 途径。顶点$v_0,v_k$ 分别称为W的起点和终点，而$v_1,\cdots ,v_i,\cdots ,v_{k-1}$ 称为W的内部顶点，W中的边数k称为W的长度。若$v_0=v_k$ ，则W称为闭途径。若途径W中，$e_1,\cdots ,e_i,\cdots ,e_k$ 互不相同，则W称为迹。若$v_0=v_k$ ，则W称为闭迹。若在迹W中，$v_0,\cdots ,v_i,\cdots ,v_k$ 互不相同，则W称为一条路。$v_0=v_k$ 的路称为一个圈，记为$C=v_0{v}_1\cdots v_i\cdots v_{k-1}{v}_k$ 。长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。

对于一个图G，如果能将图G边不相交(除端点处相交)的画在平面上，则称图G是可平面图，这个画出的无边相交的图称作图G的平面嵌入图。G的平面嵌入图将平面划分为若干连通的闭区域。这些闭区域称为G的面。有限的区域称为有限面或内部面，无限的区域称为无限面或外部面，包围面的边称为该面的边界。如果两个面有一条共同的边，则这两个面相邻。一个面与其边界上的顶点和边是关联的，如果G是2-连通可平面图，则G的每个面的边界都是圈，为方便起见，我们经常用面的边界来代替面。

Figure 1. Tubular fullerene graphs F

图1. 一类管状富勒烯图F

特别地，富勒烯图中的五边形面和六边形面分别称为5长圈和6长圈。

图G的匹配是一组两两不交的边构成的集合。如果M是一个匹配，则称M的每条边的两个端点在M下匹配，并且与M的一条边关联的每个顶点称被M覆盖。一个完美匹配是覆盖图的所有顶点的匹配。如果图G有两个完美匹配M₁和M₂，M₁和M₂如果有一条边不同，则称M₁和M₂是图G的两个不同的完美匹配。图G的完美匹配数就是图G的所有不同的完美匹配的数目，记为$f\left(G\right)$ 。

3. 主要结果及其证明

管状富勒烯图F是由同心的六边形层，两端分别加一个帽子构成，每个帽子又由一个六边形面以及六个五边形邻面构成，除了两端的帽子，其余的每个同心六边形层都由六个相邻的六边形构成(如图1所示为该类管状富勒烯图的平面嵌入图)。我们对F做一些记号，记$H_0,H_1,\cdots ,H_n$ 为F的所有同心层，这里H₀和H_n是F的最里层和最外层，都由一个六边形面构成。而H₁是和H₀相邻的由六个五边形面构成的一层，即$H_0\cup H_1$ 构成一端的帽子，$H_{n-1}\cup H_n$ 构成另一端的帽子，对于$2\le k\le n-2$ ，六边形层$H_k$ 与$H_{k-1}$ 与$H_{k+1}$ 均相邻，对$1\le k\le n$ ，我们设$C_k=H_{k-1}\cap H_k$ 。对$C_k$ 上的顶点顺时针进行标号$v_i^k$ $\left(k=1,2,\cdots ,n\right)$ ，则C₁和C_n是6长圈，$C_2,C_3,\cdots ,C_{n-1}$ 是12长圈，且$C_k=v_1^k{v}_2^k\cdots v_6^k{v}_1^k$ $\left(k=1,n\right)$ ，$C_k=v_1^k{v}_2^k\cdots v_{12}^k{v}_1^k$ $\left(k=2,3,\cdots ,n-1\right)$ ，

Figure 2. The label of tubular fullerene graphs $F_{12\left(n-1\right)}$

图2. 标号的管状富勒烯图$F_{12\left(n-1\right)}$

如图2所示。连接$C_k$ 和$C_{k+1}$ 的边称为横跨边(比如$v_1^1{v}_1^2$ 是C₁和C₂之间的一条横跨边)，$C_k$ 和$C_{k+1}$ 之间的所有横跨边构成集合，记作$E_k$ 。

本文中我们都沿用如图2所示的对管状富勒烯图F的标号，由于F由$n+1$ 层同心层构成，故F有$12\left(n-1\right)$ 个顶点，12个五边形面，$2\left(3n-8\right)$ 个六边形面。记该类管状富勒烯图为$F_{12\left(n-1\right)}\left(n\ge 3\right)$ 。

定理1的证明思路：设$ℳ$ 表示管状富勒烯图$F_{12\left(n-1\right)}$ 的所有完美匹配构成的集合，$\left|ℳ\right|$ 表示所有完美匹配的个数，C₁和C₂之间的横跨边集$E_1=\left\{v_1^1{v}_1^2,v_2^1{v}_3^2,v_3^1{v}_5^2,v_4^1{v}_7^2,v_5^1{v}_9^2,v_6^1{v}_{11}^2\right\}$ ，因为圈C₁上有偶数个点，所以对于任意一个完美匹配$M^{\prime }\in ℳ$ ，不可能为奇数，即可能取值为$0,2,4,6$ 。下面我们分别求出在每一种情况下的$F_{12\left(n-1\right)}$ 的完美匹配数，进而求和得到$\left|ℳ\right|$ 的大小。

引理2 设${ℳ}_1=\left\{M^{\prime }|M^{\prime }\in ℳ,\left|E_1\cap M^{\prime }\right|=0\right\}$ ，则$\left|{ℳ}_1\right|=2^n$ 。

证明：对任意的$M^{\prime }\in ℳ$ ，当时，6长圈$C_1=v_1^1{v}_2^1\cdots v_6^1{v}_1^1$ 上的点只能与C₁上的点匹配，则圈C₁上的完美匹配要么是$\left\{v_1^1{v}_2^1,v_3^1{v}_4^1,v_5^1{v}_6^1\right\}$ ，要么是$\left\{v_2^1{v}_3^1,v_4^1{v}_5^1,v_6^1{v}_1^1\right\}$ ，即圈C₁上有两种完美匹配。记$G_{n-1}=$ $F_{12\left(n-1\right)}-V\left(C_1\right)$ 是从图$F_{12\left(n-1\right)}$ 中删除圈C₁上的顶点后获得的子图，如图3所示。

观察图$G_{n-1}$ ，从12长圈$C_2=v_1^2{v}_2^2\cdots v_{12}^2{v}_1^2$ 上的顶点中选一个2度点，比如$v_1^2$ ，则$v_1^2$ 要么与$v_2^2$ 匹配，要么与$v_{12}^2$ 匹配。当$v_1^2$ 与$v_2^2$ 匹配时，C₂上的完美匹配为$\left\{v_1^2{v}_2^2,v_3^2{v}_4^2,v_5^2{v}_6^2,v_7^2{v}_8^2,v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\right\}$ ；当$v_1^2$ 与$v_{12}^2$ 匹配时，C₂上的完美匹配为$\left\{v_1^2{v}_{12}^2,v_{11}^2{v}_{10}^2,v_9^2{v}_8^2,v_7^2{v}_6^2,v_5^2{v}_4^2,v_3^2{v}_2^2\right\}$ ，则圈C₂上也有两种完美匹配。再把从图$G_{n-1}$ 中删除C₂上的点得到的子图，记作$G_{n-2}$ 。

对$G_{n-2}$ 进行类似对$G_{n-1}$ 的分析，依此类推，每个圈$C_k$ 上都有两种完美匹配，最后剩一个6长圈$C_n=$ $v_1^n{v}_2^n\cdots v_6^n{v}_1^n$ ，$C_n$ 也有两种完美匹配。则

$\left|{ℳ}_1\right|=2\times \underset{n-1�}{\underbrace{2\times 2\times \cdots \times 2}}=2^n$ (1)

Figure 3. Graphs $G_{n-1}$

图3. 图$G_{n-1}$

引理3 记${ℳ}_2=\left\{M^{\prime }|M^{\prime }\in ℳ,\left|E_1\cap M^{\prime }\right|=2\right\}$ ，则$\left|{ℳ}_2\right|=1+2^n{\left(2+\sqrt{3}\right)}^{n-2}+2^n{\left(2-\sqrt{3}\right)}^{n-2}$ 。

证明：对任意的$M^{\prime }\in {ℳ}_2$ ，当$\left|E_1\cap M^{\prime }\right|=2$ 时，$E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2\right\}$ 或$\left\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2\right\}$ 或$\left\{v_i^1{v}_j^2,v_{i+3}^1{v}_{j+6}^2\right\}$ ($i=1,2,\cdots ,6$ ；$j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。对上述$i,j$ ，设${ℳ}_{21}=\{M^{\prime }\in ℳ|$ $E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2\right\}\}$ ；${ℳ}_{22}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2\right\}\right\}$ ；${ℳ}_{23}=\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\{v_i^1{v}_j^2,v_{i+3}^1$ $v_{j+6}^2\}\}$ ；则${ℳ}_{2i}\cap {ℳ}_{2j}=\varnothing$ ($i,j=1,2,3$ 且$i\ne j$ )，${ℳ}_{21}\cup {ℳ}_{22}\cup {ℳ}_{23}={ℳ}_2$ 。故

$\left|{ℳ}_2\right|=\left|{ℳ}_{21}\right|+\left|{ℳ}_{22}\right|+\left|{ℳ}_{23}\right|$ (2)

设

$S_2=\left\{v_1^1,v_1^2,v_2^1,v_3^2,v_3^1,v_4^1,v_5^1,v_6^1\right\}$ ，

$S_3=\left\{v_1^1,v_1^2,v_2^1,v_3^1,v_5^2,v_4^1,v_5^1,v_6^1\right\}$ ，

$S_4=\left\{v_1^1,v_1^2,v_2^1,v_3^1,v_4^1,v_7^2,v_5^1,v_6^1\right\}$ ，

$K_{n-1}=F_{12\left(n-1\right)}-S_2$ ，

$Q_{n-1}=F_{12\left(n-1\right)}-S_3$ ，

$M_{n-1}=F_{12\left(n-1\right)}-S_4$ 。

见图4，图5所示图$K_{n-1}$ ，$Q_{n-1}$ ，$M_{n-1}$ ，记$f\left(K_{n-1}\right)$ 为子图$K_{n-1}$ 的完美匹配的数目，对$Q_{n-1}$ ，$M_{n-1}$ ，类似。

Claim 3.1 $\left|{ℳ}_{22}\right|=0$ 。

证明：因为${ℳ}_{22}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。所以圈C₁上的点$v_{i+1}^1$ 不可能被$M^{\prime }$ 覆盖($i=1,2,3,4,5,6$ )，这与$M^{\prime }$ 是完美匹配矛盾。比如当$i=1,j=1$ 时，$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_3^1{v}_5^2\right\}$ ，则圈C₁上的点$v_2^1$ 只能与圈C₂上的点$v_3^2$ 匹配，但是边$v_2^1{v}_3^2\notin E_1\cap M^{\prime }$ ，所以圈C₁上的点$v_2^1$ 不可能被$M^{\prime }$ 覆盖，则当$\left|E_1\cap M^{\prime }\right|=2$ 且${ℳ}_{22}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2\right\}\right\}$ 时，$\left|{ℳ}_{22}\right|=0$ 。

Claim 3.2 $\left|{ℳ}_{21}\right|=6f\left(K_{n-1}\right)$ 。

证明：因为${ℳ}_{21}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。当$i=1,j=1$ 时，即$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_2^1{v}_3^2\right\}$ ，C₁上剩余四个点$v_3^1,v_4^1,v_5^1,v_6^1$ 被$M^{\prime }$ 覆盖的方式只有一种，即$\left\{v_3^1{v}_4^1,v_5^1{v}_6^1\right\}\subseteq M^{\prime }$ 。因为$S_2=\left\{v_1^1,v_1^2,v_2^1,v_3^2,v_3^1,v_4^1,v_5^1,v_6^1\right\}$ ，$K_{n-1}=F_{12\left(n-1\right)}-S_2$ ，所以此时$f\left(F_{12\left(n-1\right)}\right)=f\left(K_{n-1}\right)$ (如图4所示)。

当$i=2,j=3$ 时，即$E_1\cap M^{\prime }=\left\{v_2^1{v}_3^2,v_3^1{v}_5^2\right\}$ ，C₁上剩余四个点$v_4^1,v_5^1,v_6^1,v_1^1$ 被$M^{\prime }$ 覆盖的方式只有一种，即$v_4^1{v}_5^1,v_6^1{v}_1^1\in M^{\prime }$ ，并且从$F_{12\left(n-1\right)}$ 中删除C₁上的点及$v_3^2,v_5^2$ 后获得的子图与$K_{n-1}$ 同构。因而，此时$f\left(F_{12\left(n-1\right)}\right)=f\left(K_{n-1}\right)$ 。类似地，当$i=3,4,5,6$ 时，$f\left(F_{12\left(n-1\right)}\right)=f\left(K_{n-1}\right)$ 。

综上，当$\left|E_1\cap M^{\prime }\right|=2$ 且${ℳ}_{21}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2\right\}\right\}$ 时，$\left|{ℳ}_{21}\right|=6f\left(K_{n-1}\right)$ 。

Claim 3.3 $f\left(K_{n-1}\right)=2f\left(K_{n-2}\right)+2f\left(Q_{n-2}\right)+f\left(M_{n-2}\right)$ 。

证明：观察图$K_{n-1}$ (图4)，边集$E_2=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ ，$ℳ\left(K_{n-1}\right)$ 为图$K_{n-1}$ 所有完美匹配构成的集合。对边集E₂中是完美匹配边的数目进行分类，其中$M^{″}\in ℳ\left(K_{n-1}\right)$ 。因为圈C₂在图$K_{n-1}$ 上剩余偶数个点，所以对于任意一个完美匹配$M^{″}\in ℳ\left(K_{n-1}\right)$ ，可能取值为$0,2,4,6$ 。又因$K_{n-1}$ 有一个悬挂点$v_2^2$ (即度为1的点)，因而点$v_2^2$ 必须与点$v_2^3$ 匹配，即$v_2^2{v}_2^3\in E_2\cap M^{″}$ 。因而。当或6时，因$v_2^2{v}_2^3\in E_2\cap M^{″}$ ，所以E₂中除$v_2^2{v}_2^3$ 以外剩余的五条边$v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3$ 中至少有三条边属于$M^{″}$ 。当$v_i^2{v}_i^3,v_{i+2}^2{v}_{i+2}^3$ ($i=4,6,8,10$ )属于$M^{″}$ 时，C₂上剩余点$v_{i+1}^2$ 不会被$M^{″}$ 覆盖，与$M^{″}$

Figure 4. Graphs $K_{n-1}$

图4. 图$K_{n-1}$

是$K_{n-1}$ 的完美匹配矛盾。当$v_4^2{v}_4^3,v_8^2{v}_8^3,v_{12}^2{v}_{12}^3$ 属于$M^{″}$ 时，C₂上剩余点$v_5^2,v_6^2,v_7^2$ 不会被$M^{″}$ 覆盖。同样与$M^{″}$ 是$K_{n-1}$ 的完美匹配矛盾。由此矛盾可知且。

当时，由于$v_2^2{v}_2^3\in E_2\cap M^{″}$ ，故$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3\right\}$ 或$\left\{v_2^2{v}_2^3,v_{12}^2{v}_{12}^3\right\}$ 或$\left\{v_2^2{v}_2^3,v_6^2{v}_6^3\right\}$ 或$\{v_2^2{v}_2^3,v_{10}^2{v}_{10}^3\}$ 或$\left\{v_2^2{v}_2^3,v_8^2{v}_8^3\right\}$ 。

当$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3\right\}$ 时，C₂上剩余点$v_5^2,v_6^2,v_7^2,v_8^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_5^2{v}_6^2,v_7^2{v}_8^2,$ $v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$K_{n-1}$ 中删除C₂上的点及点$v_2^3,v_4^3$ 后剩下的图同构于$K_{n-2}$ 。因而此时$K_{n-1}$ 的完美匹配数等于$K_{n-2}$ 的完美匹配数，即$f\left(K_{n-1}\right)=f\left(K_{n-2}\right)$ 。由对称性，当$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_{12}^2{v}_{12}^3\right\}$ 时，$f\left(K_{n-1}\right)=f\left(K_{n-2}\right)$ 。

当$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_6^2{v}_6^3\right\}$ 时，C₂上剩余点$v_4^2,v_5^2,v_7^2,v_8^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_4^2{v}_5^2,v_7^2{v}_8^2,$ $v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$K_{n-1}$ 中删除C₂上的点及点$v_2^3,v_6^3$ 后剩下的图同构于$Q_{n-2}$ 。因而此时$K_{n-1}$ 的完美匹配数等于$Q_{n-2}$ 的完美匹配数，即$f\left(K_{n-1}\right)=f\left(Q_{n-2}\right)$ 。由对称性，当$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_{10}^2{v}_{10}^3\right\}$ 时，$f\left(K_{n-1}\right)=f\left(Q_{n-2}\right)$ 。

当$E_2\cap M^{″}=\left\{v_2^2{v}_2^3,v_8^2{v}_8^3\right\}$ 时，C₂上剩余点$v_4^2,v_5^2,v_6^2,v_7^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_4^2{v}_5^2,v_6^2{v}_7^2,$ $v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$K_{n-1}$ 中删除C₂上的点及点$v_2^3,v_8^3$ 后剩下的图同构于$M_{n-2}$ 。因而此时$K_{n-1}$ 的完美匹配数等于$M_{n-2}$ 的完美匹配数，即$f\left(K_{n-1}\right)=f\left(M_{n-2}\right)$ 。

综上，

$f\left(K_{n-1}\right)=2f\left(K_{n-2}\right)+2f\left(Q_{n-2}\right)+f\left(M_{n-2}\right)$ (3)

Claim 3.4 $\left|{ℳ}_{23}\right|=3f\left(M_{n-1}\right)$ 。

证明：因为${ℳ}_{23}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+3}^1{v}_{j+6}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。当$i=1,j=1$ 时，即$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_4^1{v}_7^2\right\}$ 时，C₁上剩余四个点$v_2^1,v_3^1,v_5^1,v_6^1$ 被$M^{\prime }$ 覆盖的方式只有一种，即$v_2^1{v}_3^1,v_5^1{v}_6^1\in M^{\prime }$ 。从$F_{12\left(n-1\right)}$ 中删除C₁上的点及$v_1^2,v_7^2$ 后剩下的子图为$M_{n-1}$ 。故此时$f\left(F_{12\left(n-1\right)}\right)=f\left(M_{n-1}\right)$ 。由对称性，当$i=2,j=3$ 或$i=3,j=5$ 时，$f\left(F_{12\left(n-1\right)}\right)=f\left(M_{n-1}\right)$ 。当i的取值分别为4，5或6时，与i的取值分别为1，2或3时的情况重复。

所以当且${ℳ}_{23}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+3}^1{v}_{j+6}^2\right\}\right\}$ 时，$F_{12\left(n-1\right)}$ 有$\left|{ℳ}_{23}\right|=3f\left(M_{n-1}\right)$ 种完美匹配。

Claim 3.5 $f\left(M_{n-1}\right)=2f\left(K_{n-2}\right)+4f\left(Q_{n-2}\right)+3f\left(M_{n-2}\right)$ 。

证明：观察图$M_{n-1}$ (图5)，边集$E_2=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ ，设$ℳ\left(M_{n-1}\right)$ 为图$M_{n-1}$ 所有完美匹配构成的集合。对边集E₂中是完美匹配边的数目进行分类，其中$M^{″}\in ℳ\left(M_{n-1}\right)$ 。因为圈C₂在图$M_{n-1}$ 上剩余偶数个点，所以对于任意一个完美匹配$M^{″}\in ℳ\left(M_{n-1}\right)$ ，不可能为奇数，可能取值为$0,2,4,6$ 。因为在图$M_{n-1}$ 中，由点$v_2^2,v_3^2,v_4^2,v_5^2,v_6^2,v_8^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 诱导的子图是两个四长路：$v_2^2{v}_3^2{v}_4^2{v}_5^2{v}_6^2$ 和$v_8^2{v}_9^2{v}_{10}^2{v}_{11}^2{v}_{12}^2$ ，分别记作P₁和P₂。所以对任意的$M^{″}\in ℳ\left(M_{n-1}\right)$ ，。另一方面，若横跨边$v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3$ 中有两条相继的边$v_i^2{v}_i^3,v_{i+2}^2{v}_{i+2}^3$ ($i=2,4$ )属于，则路P₁上剩余一点$v_{i+1}^2$ 不会被$M^{″}$ 覆盖，矛盾。该矛盾说明$v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3$ 中不能有两条相继的边属于，同理，$v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3$ 中也不能有两条相继的边属于。这意味着。

记$E_{21}=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3\right\}$ ，$E_{22}=\left\{v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ ，则$E_{21}\cap E_{22}=\varnothing$ ，$E_{21}\cup E_{22}=E_2$ 。由前面的分析可知：$1\le \left|E_{21}\cap M^{″}\right|\le 2$ ，$1\le \left|E_{22}\cap M^{″}\right|\le 2$ (其中$M^{″}\in ℳ\left(M_{n-1}\right)$ )。所以当时，$\left|E_{21}\cap M^{″}\right|=2$ 且$\left|E_{22}\cap M^{″}\right|=2$ 。即，但P₁上剩余三个点$v_3^2,v_4^2,v_5^2$ 不可能同时被$M^{″}$ 覆盖，矛盾。该矛盾说明。

当时，$\left|E_{21}\cap M^{″}\right|=1$ 且$\left|E_{22}\cap M^{″}\right|=1$ 。由对称性，我们又分为以下三种情况：

情况1：$E_2\cap M^{″}=\left\{v_l^2{v}_l^3,v_{l+2}^2{v}_{l+2}^3\right\}$ ($l=2,4,6,8,10,12$ ，当$t>12$ 时，$v_t^2=v_{t-12}^2,v_t^3=v_{t-12}^3$ )。

因为$\left|E_{21}\cap M^{″}\right|=1$ 且$\left|E_{22}\cap M^{″}\right|=1$ 。故的取值为$\left\{v_{12}^2{v}_{12}^3,v_2^2{v}_2^3\right\}$ 或$\left\{v_6^2{v}_6^3,v_8^2{v}_8^3\right\}$ 。当$v_{12}^3,v_2^2{v}_2^3\}$ 时，C₂上剩余点$v_3^2,v_4^2,v_5^2,v_6^2,v_8^2,v_9^2,v_{10}^2,v_{11}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_3^2{v}_4^2,v_5^2{v}_6^2,v_8^2{v}_9^2,v_{10}^2{v}_{11}^2\in M^{″}$ 。从$M_{n-1}$ 中删除C₂上的点及$v_2^3,v_{12}^3$ 后剩下的图同构于$K_{n-2}$ 。因而此时$M_{n-1}$ 的完美匹配数等于$K_{n-2}$ 的完美匹配数，即$f\left(M_{n-1}\right)=f\left(K_{n-2}\right)$ 。由对称性，当时，$f\left(M_{n-1}\right)=f\left(K_{n-2}\right)$ 。

情况2：$E_2\cap M^{″}=\left\{v_l^2{v}_l^3,v_{l+4}^2{v}_{l+4}^3\right\}$ ($l=2,4,6,8,10,12$ ，当$t>12$ 时，$v_t^2=v_{t-12}^2,v_t^3=v_{t-12}^3$ )。

因为$\left|E_{21}\cap M^{″}\right|=1$ 且$\left|E_{22}\cap M^{″}\right|=1$ 。故的取值为$\left\{v_4^2{v}_4^3,v_8^2{v}_8^3\right\}$ 或$\left\{v_{12}^2{v}_{12}^3,v_4^2{v}_4^3\right\}$ 或$\left\{v_6^2{v}_6^3,v_{10}^2{v}_{10}^3\right\}$ 或$\left\{v_{10}^2{v}_{10}^3,v_2^2{v}_2^3\right\}$ 。当时，C₂上剩余点$v_2^2,v_3^2,v_5^2,v_6^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_2^2{v}_3^2,v_5^2{v}_6^2,v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$M_{n-1}$ 中删除C₂上的点及点$v_4^3,v_8^3$ 后剩下的图同构于$Q_{n-2}$ 。因而此时$M_{n-1}$ 的完美匹配数等于$Q_{n-2}$ 的完美匹配数，即$f\left(M_{n-1}\right)=f\left(Q_{n-2}\right)$ 。由对称性，当或$\left\{v_6^2{v}_6^3,v_{10}^2{v}_{10}^3\right\}$ 或$\left\{v_{10}^2{v}_{10}^3,v_2^2{v}_2^3\right\}$ 时，$f\left(M_{n-1}\right)=f\left(Q_{n-2}\right)$ 。

情况3：$E_2\cap M^{″}=\left\{v_l^2{v}_l^3,v_{l+6}^2{v}_{l+6}^3\right\}$ ($l=2,4,6,8,10,12$ ，当$t>12$ 时，$v_t^2=v_{t-12}^2,v_t^3=v_{t-12}^3$ )。

因为$\left|E_{21}\cap M^{″}\right|=1$ 且$\left|E_{22}\cap M^{″}\right|=1$ 。故的取值为$\left\{v_2^2{v}_2^3,v_8^2{v}_8^3\right\}$ 或$\left\{v_4^2{v}_4^3,v_{10}^2{v}_{10}^3\right\}$ 或$\left\{v_6^2{v}_6^3,v_{12}^2{v}_{12}^3\right\}$ 。当时，C₂上剩余点$v_3^2,v_4^2,v_5^2,v_6^2,v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式唯一，即$v_3^2{v}_4^2,v_5^2{v}_6^2,$ $v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$M_{n-1}$ 中删除C₂上的点及点$v_2^3,v_8^3$ 后剩下的图同构于$M_{n-2}$ 。因而此时$M_{n-1}$ 的完美匹配数等于$M_{n-2}$ 的完美匹配数，即$f\left(M_{n-1}\right)=f\left(M_{n-2}\right)$ 。由对称性，当或$\left\{v_6^2{v}_6^3,v_{12}^2{v}_{12}^3\right\}$ 时，$f\left(M_{n-1}\right)=f\left(M_{n-2}\right)$ 。

综上，

$f\left(M_{n-1}\right)=2f\left(K_{n-2}\right)+4f\left(Q_{n-2}\right)+3f\left(M_{n-2}\right)$ (4)

观察$Q_{n-1}$ (如图5)进行类似Claim 3.3，Claim 3.5的分析，则

$f\left(Q_{n-1}\right)=2f\left(K_{n-2}\right)+4f\left(Q_{n-2}\right)+2f\left(M_{n-2}\right)$ (5)

由(3)~(5)式得

Figure 5. Graphs $M_{n-1}$ (left), graphs $Q_{n-1}$ (right)

图5. 图$M_{n-1}$ (左)，图$Q_{n-1}$ (右)

$f\left(Q_{n-1}\right)=8f\left(K_{n-3}\right)+12f\left(Q_{n-3}\right)+8f\left(M_{n-3}\right)+4f\left(Q_{n-2}\right)$ (6)

$4f\left(Q_{n-2}\right)=8f\left(K_{n-3}\right)+16f\left(Q_{n-3}\right)+8f\left(M_{n-3}\right)$ (7)

再由(6)~(7)式得

$f\left(Q_{n-1}\right)=8f\left(Q_{n-2}\right)-4f\left(Q_{n-3}\right)$ (8)

由(3) – 2 × (5)，(4) – (5)分别得

$2f\left(K_{n-1}\right)=2f\left(K_{n-2}\right)+f\left(Q_{n-1}\right)$ (9)

$f\left(M_{n-1}\right)=f\left(M_{n-2}\right)+f\left(Q_{n-1}\right)$ (10)

由(8)，(9)得

$f\left(K_{n-1}\right)=9f\left(K_{n-2}\right)-12f\left(K_{n-3}\right)+4f\left(K_{n-4}\right)$ (11)

其中(11)式的特征方程的根为$x_1=1$ ，$x_2=4+2\sqrt{3}$ ，$x_3=4-2\sqrt{3}$ 。易知$f\left(K_2\right)=3$ ，$f\left(K_3\right)=19$ $f\left(K_4\right)=139$ 。得出递推式(11)式的通解为

$f\left(K_{n-1}\right)=\frac{1}{3}+\frac{2-\sqrt{3}}{6}{\left(4+2\sqrt{3}\right)}^{n-1}+\frac{2+\sqrt{3}}{6}{\left(4-2\sqrt{3}\right)}^{n-1}$ (12)

由(8)，(10)得

$f\left(M_{n-1}\right)=9f\left(M_{n-2}\right)-12f\left(M_{n-3}\right)+4f\left(M_{n-4}\right)$ (13)

线性递推式(13)式的特征方程的根与递推式(11)式的特征方程的根相同，易知$f\left(M_2\right)=5$ ，$f\left(M_3\right)=37$ ，$f\left(M_4\right)=277$ 。因此递推式(13)式的通解为

$f\left(M_{n-1}\right)=-\frac{1}{3}+\frac{2-\sqrt{3}}{3}{\left(4+2\sqrt{3}\right)}^{n-1}+\frac{2+\sqrt{3}}{3}{\left(4-2\sqrt{3}\right)}^{n-1}$ (14)

综上，当$\left|E_1\cap M^{\prime }\right|=2$ 时，图$F_{12\left(n-1\right)}$ 的完美匹配数为

$\begin{array}{c}\left|{ℳ}_2\right|=\left|{ℳ}_{21}\right|+\left|{ℳ}_{22}\right|+\left|{ℳ}_{23}\right|\\ =6f\left(K_{n-1}\right)+3f\left(M_{n-1}\right)\\ =1+2^n{\left(2+\sqrt{3}\right)}^{n-2}+2^n{\left(2-\sqrt{3}\right)}^{n-2}\end{array}$ (15)

引理4 记${ℳ}_3=\left\{M^{\prime }|M^{\prime }\in ℳ,\left|E_1\cap M^{\prime }\right|=4\right\}$ ，则$\left|{ℳ}_3\right|=2^n+{\left(2+\sqrt{3}\right)}^{n-2}+{\left(2-\sqrt{3}\right)}^{n-2}$ 。

证明：对任意的$M^{\prime }\in {ℳ}_3$ ，当$\left|E_1\cap M^{\prime }\right|=4$ 时，$E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+2}^1{v}_{j+4}^2,v_{i+3}^1{v}_{j+6}^2\right\}$ 或$\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2,$ $v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\}$ 或$\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。对上述$i,j$ ，设${ℳ}_{31}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+2}^1{v}_{j+4}^2,v_{i+3}^1{v}_{j+6}^2\right\}\right\}$ ，${ℳ}_{32}=\{M^{\prime }\in ℳ|E_1$ $\cap M^{\prime }=\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2,v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\}\}$ ，${ℳ}_{33}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\right\}\right\}$ 。则${ℳ}_{3i}\cap$ ${ℳ}_{3j}=\varnothing$ ($i,j=1,2,3$ 且$i\ne j$ )，${ℳ}_{31}\cup {ℳ}_{32}\cup {ℳ}_{33}={ℳ}_3$ 。故

$\left|{ℳ}_3\right|=\left|{ℳ}_{31}\right|+\left|{ℳ}_{32}\right|+\left|{ℳ}_{33}\right|$ (16)

设

$S_5=\left\{v_1^1,v_1^2,v_2^1,v_3^2,v_3^1,v_5^2,v_4^1,v_7^2,v_5^1,v_6^1\right\}$ ，

$S_6=\left\{v_1^1,v_2^1,v_3^2,v_3^1,v_5^2,v_4^1,v_7^2,v_5^1,v_6^1,v_{11}^2\right\}$ ，

$S_7=\left\{v_1^1,v_2^1,v_3^2,v_3^1,v_5^2,v_4^1,v_5^1,v_9^2,v_6^1,v_{11}^2\right\}$ ，

$N_{n-1}=F_{12\left(n-1\right)}-S_5$ ，

$R_{n-1}=F_{12\left(n-1\right)}-S_6$ ，

$X_{n-1}=F_{12\left(n-1\right)}-S_7$ 。

见图6，图7所示图$N_{n-1}$ ，$R_{n-1}$ ，$X_{n-1}$ 。记$f\left(N_{n-1}\right)$ 为子图$N_{n-1}$ 的完美匹配的数目，对$R_{n-1}$ ，$X_{n-1}$ 类似。

Claim 4.1 $\left|{ℳ}_{32}\right|=0$ 。

证明：因为${ℳ}_{32}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+2}^1{v}_{j+4}^2,v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。所以此时$v_{i+1}^1$ 必须与$v_{j+2}^2$ 匹配。与$\left|E_1\cap M^{\prime }\right|=4$ 矛盾，因而$\left|{ℳ}_{32}\right|=0$ 。比如当$i=1,j=1$ 时，$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_3^1{v}_5^2,v_4^1{v}_7^2,v_5^1{v}_9^2\right\}$ ，则C₁上剩余点$v_2^1,v_6^1$ 必须分别与$v_3^2,v_{11}^2$ 匹配，此时$v_2^1{v}_3^2,v_6^1{v}_{11}^2\in E_1\cap M^{\prime }$ ，与$\left|E_1\cap M^{\prime }\right|=4$ 矛盾。

Claim 4.2 $\left|{ℳ}_{33}\right|=0$ 。

证明：因为${ℳ}_{33}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+3}^1{v}_{j+6}^2,v_{i+4}^1{v}_{j+8}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当

$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。所以此时$v_{i+2}^1$ 必须与$v_{j+4}^2$ 匹配。与$\left|E_1\cap M^{\prime }\right|=4$ 矛盾，因而$\left|{ℳ}_{33}\right|=0$ 。比如当$i=1,j=1$ 时，$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_2^1{v}_3^2,v_4^1{v}_7^2,v_5^1{v}_9^2\right\}$ ，则C₁上剩余点$v_3^1,v_6^1$ 必须分别与$v_5^2,v_{11}^2$ 匹

配，此时$v_3^1{v}_5^2,v_6^1{v}_{11}^2\in E_1\cap M^{\prime }$ ，与$\left|E_1\cap M^{\prime }\right|=4$ 矛盾。

Claim 4.3 $\left|{ℳ}_{31}\right|=6f\left(N_{n-1}\right)$ 。

证明：因为${ℳ}_{31}=\left\{M^{\prime }\in ℳ|E_1\cap M^{\prime }=\left\{v_i^1{v}_j^2,v_{i+1}^1{v}_{j+2}^2,v_{i+2}^1{v}_{j+4}^2,v_{i+3}^1{v}_{j+6}^2\right\}\right\}$ ($i=1,2,\cdots ,6;j=1,3,5,7,9,11$ ，当$l>6$ 时，$v_l^1=v_{l-6}^1$ ；当$t>12$ 时，$v_t^2=v_{t-12}^2$ )。当$i=1,j=1$ 时，$E_1\cap M^{\prime }=\left\{v_1^1{v}_1^2,v_2^1{v}_3^2,v_3^1{v}_5^2,v_4^1{v}_7^2\right\}$ ，C₁上剩余两个点$v_5^1,v_6^1$ 被$M^{\prime }$ 覆盖的方式只有一种，即$v_5^1{v}_6^1\in M^{\prime }$ 。因为$S_5=\left\{v_1^1,v_1^2,v_2^1,v_3^2,v_3^1,v_5^2,v_4^1,v_7^2,v_5^1,v_6^1\right\}$ ，$N_{n-1}=F_{12\left(n-1\right)}-S_5$ 。从$F_{12\left(n-1\right)}$ 中删除$V\left(C_1\right)$ 及点$v_1^2,v_3^2,v_5^2,v_7^2$ 后剩下的图即为$N_{n-1}$ 。因而此时$f\left(F_{12\left(n-1\right)}\right)=f\left(N_{n-1}\right)$ ，由对称性，当$i=2,3,4,5,6$ 时，$f\left(F_{12\left(n-1\right)}\right)=f\left(N_{n-1}\right)$ ，所以$\left|{ℳ}_{31}\right|=6f\left(N_{n-1}\right)$ 。

Figure 6. Graphs $N_{n-1}$

图6. 图$N_{n-1}$

Claim 4.4 $f\left(N_{n-1}\right)=2f\left(N_{n-2}\right)+f\left(R_{n-2}\right)$ 。

证明：观察图$N_{n-1}$ (如图6)，边集$E_2=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ ，设$ℳ\left(N_{n-1}\right)$ 为图$N_{n-1}$ 所有完美匹配构成的集合。对边集E₂中是完美匹配边的数目进行分类，其中$M^{″}\in ℳ\left(N_{n-1}\right)$ 。因为圈C₂在图$N_{n-1}$ 上剩余偶数个点，所以对于任意一个完美匹配$M^{″}\in ℳ\left(N_{n-1}\right)$ ，不可能为奇数，可能取值为$0,2,4,6$ 。

对图$N_{n-1}$ ，点$v_2^2$ 必须与点$v_2^3$ 匹配，点$v_4^2$ 必须与点$v_4^3$ 匹配，点$v_6^2$ 必须与点$v_6^3$ 匹配，则边集$\{v_2^2{v}_2^3,v_4^2{v}_4^3,$ $v_6^2{v}_6^3\}\subseteq E_2\cap M^{″}$ ，所以可能取值为4或6。又当时，即$v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,$ $v_{12}^2{v}_{12}^3\in E_2\cap M^{″}$ ，则圈C₂上点$v_9^2,v_{11}^2$ 不能被$M^{″}$ 覆盖，矛盾。从而。

对任意$M^{″}\in ℳ\left(N_{n-1}\right)$ ，当时，由于$v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3\in E_2\cap M^{″}$ ，故$E_2\cap M^{″}=\{v_2^2{v}_2^3,v_4^2{v}_4^3,$ $v_6^2{v}_6^3,v_8^2{v}_8^3\}$ 或$\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_{10}^2{v}_{10}^3\}$ 或$\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_{12}^2{v}_{12}^3\}$ 。当$E_2\cap M^{″}=\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3\}$ 时，则圈C₂上点$v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式只有一种，即$v_9^2{v}_{10}^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$N_{n-1}$ 中删除$E_2\cap M^{″}$ 中边关联的点以及点$v_9^2,v_{10}^2,v_{11}^2,v_{12}^2$ 后剩下的图同构于$N_{n-2}$ ，因而此时$f\left(N_{n-1}\right)=f\left(N_{n-2}\right)$ 。由对称性，当$E_2\cap M^{″}=$ $\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_{12}^2{v}_{12}^3\}$ 时，$f\left(N_{n-1}\right)=f\left(N_{n-2}\right)$ 。当$E_2\cap M^{″}=\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_{10}^2{v}_{10}^3\}$ 时，则圈C₂上点$v_8^2,v_9^2,v_{11}^2,v_{12}^2$ 被$M^{″}$ 覆盖的方式只有一种，即$v_8^2{v}_9^2,v_{11}^2{v}_{12}^2\in M^{″}$ 。从$N_{n-1}$ 中删除$E_2\cap M^{″}$ 中边关联的点以及点$v_8^2,v_9^2,v_{11}^2,v_{12}^2$ 后剩下的图同构于$R_{n-2}$ ，因而此时$f\left(N_{n-1}\right)=f\left(R_{n-2}\right)$ 。

综上，

$f\left(N_{n-1}\right)=2f\left(N_{n-2}\right)+f\left(R_{n-2}\right)$ (17)

Claim 4.5 $f\left(R_{n-1}\right)=f\left(N_{n-2}\right)+2f\left(R_{n-2}\right)+f\left(X_{n-2}\right)$ 。

证明：观察图$R_{n-1}$ (如图7)，边集$E_2=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ ，设$ℳ\left(R_{n-1}\right)$ 为图$R_{n-1}$ 所有完美匹配构成的集合。对边集E₂中是完美匹配边的数目进行分类，其中$M^{″}\in ℳ\left(R_{n-1}\right)$ 。因为圈C₂在图$R_{n-1}$ 上剩余偶数个点，所以对于任意一个完美匹配$M^{″}\in ℳ\left(R_{n-1}\right)$ ，不可能为奇数，可能取值为$0,2,4,6$ 。且在图$R_{n-1}$ 中，圈C₂被分成两个2-长路$v_8^2{v}_9^2{v}_{10}^2,v_{12}^2{v}_1^2{v}_2^2$ 和两个孤立点$v_4^2,v_6^2$ (见图7左)。

所以对任意$M^{″}\in ℳ\left(R_{n-1}\right)$ ，且$v_8^2{v}_8^3,v_{10}^2{v}_{10}^3$ 中恰好有一条边属于，同理，

Figure 7. Graphs $R_{n-1}$ (left), graphs $X_{n-1}$ (right)

图7. 图$R_{n-1}$ (左)，图$X_{n-1}$ (右)

$v_{12}^2{v}_{12}^3,$ $v_2^2{v}_2^3$ 中恰好有一条边也属于，为此，我们有且$E_2\cap M^{″}=\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_2^2{v}_2^3\right\}$ 或$\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_{10}^2{v}_{10}^3,v_2^2{v}_2^3\right\}$ 或$\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{12}^2{v}_{12}^3\right\}$ 或$\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ 。当$E_2\cap M^{″}=\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_2^2{v}_2^3\right\}$ 时，圈C₂上点$v_9^2,v_{10}^2,v_{12}^2,v_1^2$ 被$M^{″}$ 覆盖的方式只有一种，即$v_9^2{v}_{10}^2,v_{12}^2{v}_1^2\in M^{″}$ 。从$R_{n-1}$ 中删除中边关联的点以及点$v_9^2,v_{10}^2,v_{12}^2,v_1^2$ 后剩下的图同构于$N_{n-2}$ ，因而此时$f\left(R_{n-1}\right)=f\left(N_{n-2}\right)$ 。当$E_2\cap M^{″}=\{v_4^2{v}_4^3,$ $v_6^2{v}_6^3,v_2^2{v}_2^3,v_{10}^2{v}_{10}^3\}$ 时，圈C₂上点$v_8^2,v_9^2,v_{12}^2,v_1^2$ 被$M^{″}$ 覆盖的方式只有一种，即$v_8^2{v}_9^2,v_{12}^2{v}_1^2\in M^{″}$ 。从$R_{n-1}$ 中删除中边关联的点以及点$v_8^2,v_9^2,v_{12}^2,v_1^2$ 后剩下的图同构于$R_{n-2}$ ，因而此时$f\left(R_{n-1}\right)=f\left(R_{n-2}\right)$ 。由对称性，当$E_2\cap M^{″}=\left\{v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{12}^2{v}_{12}^3\right\}$ 时，$f\left(R_{n-1}\right)=f\left(R_{n-2}\right)$ 。当时，圈C₂上点$v_8^2,v_9^2,v_1^2,v_2^2$ 被$M^{″}$ 覆盖的方式只有一种，即$v_8^2{v}_9^2,v_1^2{v}_2^2\in M^{″}$ 。从$R_{n-1}$ 中删除中边关联的点以及点$v_8^2,v_9^2,v_1^2,v_2^2$ 后剩下的图同构于$X_{n-2}$ ，因而此时$f\left(R_{n-1}\right)=f\left(X_{n-2}\right)$ 。

综上，

$f\left(R_{n-1}\right)=f\left(N_{n-2}\right)+2f\left(R_{n-2}\right)+f\left(X_{n-2}\right)$ (18)

观察$X_{n-1}$ (如图7)进行类似Claim 4.4，Claim 4.5的分析，可得

$f\left(X_{n-1}\right)=2f\left(X_{n-2}\right)+2f\left(R_{n-2}\right)$ (19)

由(17)~(19)式得

$f\left(R_{n-1}\right)=2f\left(N_{n-3}\right)+2f\left(X_{n-3}\right)+3f\left(R_{n-3}\right)+2f\left(R_{n-2}\right)$ (20)

$2f\left(R_{n-2}\right)=2f\left(N_{n-3}\right)+2f\left(X_{n-3}\right)+4f\left(R_{n-3}\right)$ (21)

再由(20)~(21)式得

$f\left(R_{n-1}\right)=4f\left(R_{n-2}\right)-f\left(R_{n-3}\right)$ (22)

由(17)，(22)联立得

$f\left(N_{n-1}\right)=6f\left(N_{n-2}\right)-9f\left(N_{n-3}\right)+2f\left(N_{n-4}\right)$ (23)

其中(23)式的特征方程的根为$x_1=2$ ，$x_2=2+\sqrt{3}$ ，$x_3=2-\sqrt{3}$ 。易知$f\left(N_2\right)=2$ ，$f\left(N_3\right)=3$ $f\left(N_4\right)=14$ 。得出递推式(23)式的通解为

$f\left(N_{n-1}\right)=\frac{2^{n-1}}{3}+\frac{2-\sqrt{3}}{6}{\left(2+\sqrt{3}\right)}^{n-1}+\frac{2+\sqrt{3}}{6}{\left(2-\sqrt{3}\right)}^{n-1}$ (24)

故对任意的$M^{\prime }\in ℳ$ ，当$\left|E_1\cap M^{\prime }\right|=4$ 时，图$F_{12\left(n-1\right)}$ 的完美匹配数为

$\begin{array}{c}\left|{ℳ}_3\right|=\left|{ℳ}_{31}\right|+\left|{ℳ}_{32}\right|+\left|{ℳ}_{33}\right|\\ =6f\left(N_{n-1}\right)\\ =2^n+{\left(2+\sqrt{3}\right)}^{n-2}+{\left(2-\sqrt{3}\right)}^{n-2}\end{array}$ (25)

引理5 令${ℳ}_4=\left\{M^{\prime }|M^{\prime }\in ℳ,\left|E_1\cap M^{\prime }\right|=6\right\}$ ，则$\left|{ℳ}_4\right|=1$ 。

证明：当${ℳ}_4=\left\{M^{\prime }|M^{\prime }\in ℳ,\left|E_1\cap M^{\prime }\right|=6\right\}$ 时，即C₁和C₂之间的横跨边$E_1=\{v_1^1{v}_1^2,v_2^1{v}_3^2,v_3^1{v}_5^2,v_4^1{v}_7^2,v_5^1{v}_9^2,v_6^1$ $v_{11}^2\}$ 是完美匹配$M^{\prime }$ 中的边。从图$F_{12\left(n-1\right)}$ 中删除横跨边$E_1=\{v_1^1{v}_1^2,v_2^1{v}_3^2,v_3^1{v}_5^2,v_4^1{v}_7^2,v_5^1{v}_9^2,v_6^1{v}_{11}^2\}$ 中的边关联的点得到图$W_{n-1}$ (如图8左所示)，则C₂和C₃之间的横跨边$E_2=\left\{v_2^2{v}_2^3,v_4^2{v}_4^3,v_6^2{v}_6^3,v_8^2{v}_8^3,v_{10}^2{v}_{10}^3,v_{12}^2{v}_{12}^3\right\}$ 也是完美匹配$M^{\prime }$ 中的边。再从图$W_{n-1}$ 中删除横跨边E₂中的边关联的点得到图$W_{n-2}$ ，则C₃和C₄之间的横跨边E₃也是完美匹配$M^{\prime }$ 中的边。依此类推，最后$C_{n-1}$ 和$C_n$ 之间的横跨边$E_{n-1}=\left\{v_2^{n-1}{v}_1^n,v_4^{n-1}{v}_2^n,v_6^{n-1}{v}_3^n,v_8^{n-1}{v}_4^n,v_{10}^{n-1}{v}_5^n,v_{12}^{n-1}{v}_6^n\right\}$ 也是完美匹配$M^{\prime }$ 中的边。则$\left|E_1\cap M^{\prime }\right|=6$ 时，图$F_{12\left(n-1\right)}$ 的完美匹配如图8右所示。

即当$\left|E_1\cap M^{\prime }\right|=6$ 时，图$F_{12\left(n-1\right)}$ 的完美匹配数为

$\left|{ℳ}_4\right|=1$ (26)

Figure 8. Graphs $W_{n-1}$ (left), a perfect matching of graphs $F_{12\left(n-1\right)}$ (right)

图8. 图$W_{n-1}$ (左)，图$F_{12\left(n-1\right)}$ 的一种完美匹配(右)

定理1的证明：结合引理2~5，可得

$\begin{array}{c}\left|ℳ\right|=\left|{ℳ}_1\right|+\left|{ℳ}_2\right|+\left|{ℳ}_3\right|+\left|{ℳ}_4\right|\\ =2^n+\left[1+2^n{\left(2+\sqrt{3}\right)}^{n-2}+2^n{\left(2-\sqrt{3}\right)}^{n-2}\right]+\left[2^n+{\left(2+\sqrt{3}\right)}^{n-2}+{\left(2-\sqrt{3}\right)}^{n-2}\right]+1\\ =\left[2+{\left(2+\sqrt{3}\right)}^{n-2}+{\left(2-\sqrt{3}\right)}^{n-2}\right]\left(2^n+1\right)\end{array}$ (27)

设s是F的顶点数，则$s=12\left(n-1\right)$ ，即$n=\frac{s+12}{12}$ 代入等式(27)，可得

$\left|ℳ\right|=\left[2+{\left(2+\sqrt{3}\right)}^{\frac{s-12}{12}}+{\left(2-\sqrt{3}\right)}^{\frac{s-12}{12}}\right]\left(2^{\frac{s+12}{12}}+1\right)$ (28)

即图F的完美匹配数为$\left[2+{\left(2+\sqrt{3}\right)}^{\frac{s-12}{12}}+{\left(2-\sqrt{3}\right)}^{\frac{s-12}{12}}\right]\left(2^{\frac{s+12}{12}}+1\right)$ (其中s为F的顶点数)。

4. 结论

在本文中，我们得出一类管状富勒烯图F的完美匹配数的计算公式，验证了Lovász和Plummer的任意2-边连通3-正则图都有指数多个完美匹配的猜想的正确性。对于其他管状富勒烯图，我们可以尝试运用本文中的方法求出其完美匹配数的计算公式。在推导文中的递推公式时过程比较繁琐，后续可以寻求更好的方法解决此类问题。

基金项目

本文研究得到了国家自然科学基金项目(No.11801148, 11626089)以及河南理工大学博士基金项目(No.B2014-060)的资助。

NOTES

^*通讯作者。