n维扭曲立方体是超k-匹配图

doi:10.12677/aam.2025.145285

期刊菜单

n维扭曲立方体是超k-匹配图
The TQ_n Is Super k-Matching Graph

DOI: 10.12677/aam.2025.145285, PDF, HTML, XML,
作者: 宗政, 胡晓敏：太原理工大学数学学院，山西太原
关键词: 超强整数-匹配；；几乎完美整数-匹配；完美整数-匹配；Super Strong Integer -Matching；； Almost Perfect Integer -Matching； Perfect Integer -Matching

摘要: 图

G

的整数

k

-匹配是由

E (G)

到

{0, 1, \dots, k}

上的映射

f

，满足对任意点

u

，所有

f (e)

的加和不超过

k

，其中

f (e)

之和为所有以点

u

为端点的边

e

。当

k = 1

时，整数

k

-匹配即为匹配。(强)整数

k

-匹配排除数由

m p^{k} (G)

(s m p^{k} (G))

表示，是被一个图删去后该图既不存在完美整数

k

-匹配，也不存在几乎完美整数

k

-匹配的最小点集(点集与边集)的元素数。Caibing Chang、Xianfu Li and Yan Liu介绍了

s m p^{k} (T Q_{n})

。本文提出超强整数

k

-匹配的定义并证明

T Q_{n}

是超强整数

k

-匹配图。

Abstract: An integer

k

-matching of a graph

G

is a function

f

from

E (G)

{0, 1, \dots, k}

such that the sum of

f (e)

is not more than

k

for any vertex

u

, where the sum of

f (e)

is taken over all edges

e

incident to

u

. When

k = 1

, the integer

k

-matching is a matching. The (strong) integer

k

-matching preclusion number, denoted by

m p^{k} (G)

(s m p^{k} (G))

, is the number of elements of the minimum vertex (vertices and edges) whose deletion results in a graph with neither perfect integer

k

-matching nor almost perfect integer

k

-matching. The

s m p^{k} (T Q_{n})

was introduced by Caibing Chang, Xianfu Li and Yan Liu. In this paper, we denote the super strong integer

k

-matching and prove that

T Q_{n}

is super strong integer

k

-matching graph.

文章引用：宗政, 胡晓敏. n维扭曲立方体是超k-匹配图[J]. 应用数学进展, 2025, 14(5): 589-600. https://doi.org/10.12677/aam.2025.145285

1. 引言

分布式网络目前得到广泛应用，网络拓扑结构的设计与优化成为研究热点。网络拓扑的可靠性直接影响到系统的容错性和性能，因此，如何设计具有高可靠性和强容错能力的网络结构成为了一个重要课题。超立方体具备正则性、高容错性、对称性，受到了广泛关注。n维扭曲立方体( $T Q_{n}$ )基于超立方体构建，具有对称性和高连通性，能够确保网络的稳定运行。本文旨在研究n维扭曲立方体( $T Q_{n}$ )是超强整数 $k$ -匹配图，为大规模并行计算系统和分布式网络的拓扑设计提供理论支持。

Cheng等人在[1]中研究了某些互联网络的匹配排除集，在[2]中研究了交替群图的匹配排除及其推广，在[3]中研究了条件匹配排除集；刘燕等人在[4]中提出了整数k-匹配与强整数k-匹配的概念。

整数k-匹配作为近几年新提出的概念，已经吸引诸多学者研究讨论，如n-维扭曲立方体与S_n_,_s的整数k-匹配排除数和它们的强整数k-匹配排除数、图的 $A_{α}$ -谱半径与整数 $k$ -匹配排除数的关系等，这些成果为图论的研究进程作出了贡献。

2. 预备知识

2.1. 术语和概念

设 $G = (V (G), E (G))$ 是一个简单有限图，其中 $V (G)$ 表示点集， $E (G)$ 表示边集。 $(x, y)$ 表示点 $x$ 和点 $y$ 之间的边，文中有时简记为 $x y$ 。对于任意的点 $u \in V (G)$ ，用 $N_{G} (u) = {w \in V (G) | (u, w) \in E (G)}$ 表示 $u$ 在 $G$ 中的邻点集，用 $d (u) = | N_{G} (u) |$ 表示 $u$ 在图 $G$ 中的度。对于图 $G$ 的顶点集 $S$ ，用 $N_{G} (S) = {w \in V (G) \ S | \exists u \in S, (u, w) \in E (G)}$ 表示 $S$ 的开邻集， $N [S] = N (S) \cup S$ 表示 $S$ 的闭邻集。当图 $G$ 可以从文中清楚看出时，用 $N (u)$ 代替 $N_{G} (u)$ ，用 $N (S)$ 代替 $N_{G} (S)$ 。对于图 $G$ 的两个顶点集 $A$ 和 $B$ ，用 $E (A, B) = {(x, y) | x \in A, y \in B}$ 表示 $A$ 和 $B$ 之间的边集，用 $| E (A, B) |$ 表示顶点集 $A$ 和 $B$ 之间的边数。用 $G [H]$ 表示由 $H$ 在 $G$ 中诱导的子图。令圈 $C$ 上的点 $u$ 沿顺时针方向的继点为 $u^{'}$ 。

2.2. $T Q_{n}$ 的定义

$n$ 为奇数， $V (T Q_{n}) = {u_{n - 1} u_{n - 2} \dots u_{0} : u_{i} \in {0, 1}, 0 \leq i \leq n - 1}$ ，则 $| V (T Q_{n}) | = 2^{n}$ [1]。如果 $u_{n - 1} + u_{n - 2} + \dots + u_{0}$ 为偶数，那么点 $u_{n - 1} u_{n - 2} \dots u_{0}$ 被称为偶点。否则，该点称为奇点。注意到 $T Q_{1} = K_{2}$ 。假设 $n \geq 3$ 并且 $T Q_{n - 2}$ 也按照这种方式定义。令 $U = u_{n - 1} u_{n - 2} \dots u_{0} \in V (T Q_{n - 2})$ 。则 $T Q_{n}$ 的点 $i j u_{n - 3} u_{n - 4} \dots u_{0}$ 简单定义为 $i j U$ ，其中 $i, j \in {0, 1}$ 。令 $V_{i j} = {i j U | U \in V (T Q_{n - 2})}$ 。设 $T Q_{n} [V_{i j}] = i j T Q_{n - 2}$ ，称其为子扭曲立方体并且它与 $T Q_{n - 2}$ 同构。那么 $T Q_{n}$ 由四个子扭曲立方体 $00 T Q_{n - 2}$ 、 $10 T Q_{n - 2}$ 、 $01 T Q_{n - 2}$ 和 $11 T Q_{n - 2}$ (简记为 $H_{1}$ 、 $H_{2}$ 、 $H_{3}$ 、 $H_{4}$ )构成。两个不同子扭曲立方体之间的边被称为交叉边。令 $C (E)$ 为 $T Q_{n}$ 的交叉边集并定义 $\bar{i} = 1 - i$ ，其中 $i \in {0, 1}$ 。对任意 $i, j \in {0, 1}$ ，定义：

$\begin{array}{l} C (E) = {(i j U, \bar{i} j U) : U \in V (T Q_{n - 2})} \cup {(i j U, \bar{i} \bar{j} U) : U \in V (T Q_{n - 2}) 且 U 是偶点} \\ \cup {(i j U, i \bar{j} U) : U \in V (T Q_{n - 2}) 且 U 是奇点} \end{array}$

Figure 1. $T Q_{n}$

图1. n维扭曲立方体

根据 $C (E)$ 的定义， $i j T Q_{n - 2}$ 的每一点 $i j U$ 在 $T Q_{n - 2}$ 中有两个邻点 $\bar{i} j U$ 与 $\bar{i} \bar{j} U$ (或 $i \bar{j} U$ )并且它们在不同的子扭曲立方体中，称它们为 $i j U$ 的外邻点。如果 $u$ 在 $i j V (T Q_{n - 2})$ 中有外邻点，我们称子扭曲立方体 $i j V (T Q_{n - 2})$ 与点 $u$ 相邻。则 $T Q_{n}$ 的每一个点与一个子扭曲立方体不相邻。根据 $T Q_{n}$ 的定义， $T Q_{n}$ 为n-正则并且 $i j T Q_{n - 2}$ 的每一个点有 $2^{n - 1}$ 个外邻点。如图1所示。

可以得到 $| E (H_{1}, H_{2}) | = | E (H_{3}, H_{4}) | = 2^{n - 2}$ ， $| E (H_{1}, H_{3}) | = | E (H_{1}, H_{4}) | = | E (H_{2}, H_{3}) | = | E (H_{2}, H_{4}) | = 2^{n - 3}$ 。

定义2.1：图 $G$ 的匹配是由 $E (G)$ 到 ${0, 1}$ 的一个映射 $f$ ，满足对任意点 $u$ ， $\sum_{e ~ u} f (e) \leq 1$ ，其中 $e ~ u$ 表示 $e$ 是 $u$ 的端点。如果对任意点 $u$ ， $\sum_{e ~ u} f (e) = 1$ ，则 $f$ 为完美匹配。如果存在一点 $v$ ， $\sum_{e ~ v} f (e) = 0$ 并且其他任意点 $u$ ，满足 $\sum_{e ~ u} f (e) = 1$ ，则匹配 $f$ 为几乎完美匹配。 $F \subset V (G) \cup E (G)$ ，如果 $G - F$ 既不存在完美匹配，也不存在几乎完美匹配，则 $F$ 为 $G$ 的强匹配排除集[2]。 $F$ 为 $G$ 的最小强匹配排除集， $| F |$ 即为 $G$ 的强匹配排除数(简记为 $s m p (G)$ )。

定义2.2： $h$ 是由 $E (G)$ 到 ${0, 1, \dots, k}$ 的映射，满足对任意点 $u$ ， $\sum_{e ~ u} f (e) \leq k$ ，则 $h$ 为整数 $k$ -匹配。整数 $k$ -匹配 $h$ 满足对任意点 $u$ ， $\sum_{e ~ u} f (e) \leq k$ ，整数 $k$ 匹配 $h$ 为完美整数 $k$ 匹配。整数 $k$ -匹配 $h$ 满足存在一点 $v$ ， $\sum_{e ~ v} f (e) = k - 1$ 并且其他任意点 $u$ ，满足 $\sum_{e ~ u} f (e) = k$ ，则匹配 $f$ 为几乎完美整数 $k$ 匹配。 $F \subset V (G) \cup E (G)$ ，如果 $G - F$ 既不存在完美整数 $k$ -匹配，也不存在几乎完美整数 $k$ -匹配，则 $F$ 为 $G$ 的强整数 $k$ 匹配排除集。 $F$ 为 $G$ 的最小强整数 $k$ -匹配排除集， $| F |$ 即为 $G$ 的强整数 $k$ -匹配排除数(简记为 $s m p^{k} (G)$ ) [3] [5]-[7]。

定义2.3： $G$ 的任意最小强整数 $k$ 匹配排除集 $F$ ， $F \subset V (G) \cup E (G)$ ，如果 $G - F$ 存在有且仅有一个孤立点，则称 $G$ 为超强整数 $k$ 匹配图。显然，图G₁为超强整数 $k$ 匹配图。

超强整数 $k$ 匹配图的提出有助于更好地刻画某个图的强整数k-匹配排除集的结构，为片上网络、数据中心网络以及超级计算机互连等领域提供理论支撑。

由上述定义，我们可以得到 $m p^{1} (G) = m p (G)$ 与 $s m p^{1} (G) = s m p (G)$ 。于是我们仅考虑 $k \geq 2$ 的情况。当 $k \geq 2$ 时，由于对任一点 $v$ ，与 $v$ 相邻的点集为整数 $k$ -匹配排除集，所以 $s m p^{k} (G) \leq m p^{k} (G) \leq δ (G)$ 。在[4]中，我们知道当 $k$ 为偶数时， $G$ 存在完美整数 $k$ -匹配当且仅当 $G$ 存在完美分数匹配。当 $G$ 有一个几乎完美整数 $k$ -匹配 $h$ 时，因为 $\sum_{e \in E (G)} h (e) = \frac{k | V (G) | - 1}{2}$ 是整数，所以 $k$ 为奇数并且 $| V (G) |$ 为奇数。因此，对于任一偶数 $k$ ， $m p^{k} (G) = f m p (G)$ 并且 $s m p^{k} (G) = f s m p (G)$ 。所以我们可以假设 $k \geq 3$ 为奇数。而且我们知道，如果 $G$ 有一个完美整数 $k$ -匹配，则 $| V (G) |$ 为偶数。如果 $G$ 有一个几乎完美整数 $k$ -匹配，则 $| V (G) |$ 为奇数。

根据匹配的定义，当图G有完美匹配时，图G就有完美整数k-匹配。

当k为奇数时，如果图G有一个奇数阶哈密顿圈C，对C的边交替赋值 $\frac{k - 1}{2}$ 与 $\frac{k + 1}{2}$ ，则图G有一个几乎完美整数k-匹配；如果图G有一个偶数阶哈密顿圈C，对C的边交替赋值 $k$ 与0，则图G有一个完美整数k-匹配；如果图G有一个偶数阶哈密顿圈P，对P的边交替赋值 $k$ 与0，则图G有一个完美整数k-匹配。

引理2.4：当 $n \geq 3$ 时， $F \subset V (G) \cup E (G)$ 并且 $| F | \leq n - 2$ ，则 $T Q_{n}$ 是哈密顿图。

定理2.5：当 $n \geq 7$ 时， $T Q_{n}$ 是超强整数 $k$ 匹配图。

证明：我们通过证明任意集合 $F \subset V (G) \cup E (G)$ ， $| F | \leq δ (G) = n$ ， $G - F$ 或者存在孤立点，或者存在完美整数 $k$ -匹配，或者存在几乎完美整数 $k$ -匹配来证明定理。

记 $F_{i} = F \cap H_{i}$ ， $G_{i} = H_{i} - F_{i}$ 。根据 $T Q_{n}$ 的对称性，假设 $| F_{1} | \geq | F_{2} | \geq | F_{3} | \geq | F_{4} |$ 。我们通过讨论 $| F_{1} |$ 的大小来证明引理。

情况1： $| F_{1} | \leq n - 4$

因为 $| F_{1} | \geq | F_{2} | \geq | F_{3} | \geq | F_{4} |$ ，所以根据引理2.4， $G_{1}$ 有哈密顿圈 $C_{1}$ ， $G_{2}$ 有哈密顿圈 $C_{2}$ ， $G_{3}$ 有哈密顿圈 $C_{3}$ ， $G_{4}$ 有哈密顿圈 $C_{4}$ 。

情况1.1： $G_{1}$ 是偶图， $G_{2}$ 是偶图， $G_{3}$ 是偶图， $G_{4}$ 是偶图。

$G_{1}$ 有偶数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G - F$ 有一个完美整数 $k$ -匹配。

情况1.2： $G_{1}$ 是奇图， $G_{2}$ 是偶图， $G_{3}$ 是偶图， $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况1.3： $G_{1}$ 与 $G_{2}$ 是奇图， $G_{3}$ 与 $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G_{3} \cup G_{4}$ 有一个完美匹配。

当 $n \geq 7$ 时，因为 $| E (H_{1}, H_{2}) | = 2^{n - 2} > n$ ，所以 $| E (G_{1}, G_{2}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{1})$ ， $v_{2} \in V (G_{2})$ ，则 $G_{1} \cup G_{2}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{1} v_{1} v_{2} C_{2} {v^{'}}_{2}$ 。所以 $G_{1} \cup G_{2}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况1.4： $G_{1}$ 与 $G_{3}$ 是奇图， $G_{2}$ 与 $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G_{2} \cup G_{4}$ 有一个完美匹配。当 $n \geq 7$ 时，因为 $| E (H_{1}, H_{3}) | = 2^{n - 3} > n$ ，所以 $| E (G_{1}, G_{3}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{1})$ ， $v_{2} \in V (G_{3})$ ，则 $G_{1} \cup G_{3}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{1} v_{1} v_{2} C_{3} {v^{'}}_{2}$ 。所以 $G_{1} \cup G_{3}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况1.5： $G_{1}$ 、 $G_{2}$ 、 $G_{3}$ 是奇图， $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G_{3}$ 有一个几乎完美整数 $k$ -匹配， $G_{4}$ 有一个完美匹配。当 $n \geq 7$ 时，因为 $| E (H_{1}, H_{2}) | = 2^{n - 2} > n$ ，所以 $| E (G_{1}, G_{2}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{1})$ ， $v_{2} \in V (G_{2})$ ，则 $G_{1} \cup G_{2}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{1} v_{1} v_{2} C_{2} {v^{'}}_{2}$ 。所以 $G_{1} \cup G_{2}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况1.6： $G_{1}$ ， $G_{2}$ ， $G_{3}$ 与 $G_{4}$ 均为奇图。

$G_{1}$ 有奇数阶哈密顿圈 $C_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有奇数阶哈密顿圈 $C_{4}$ 。当 $n \geq 7$ 时，因为 $| E (H_{1}, H_{2}) | = 2^{n - 2} > n$ ，所以 $| E (G_{1}, G_{2}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{1})$ ， $v_{2} \in V (G_{2})$ ，则 $G_{1} \cup G_{2}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{1} v_{1} v_{2} C_{2} {v^{'}}_{2}$ 。所以 $G_{1} \cup G_{2}$ 有一个完美匹配。同理， $G_{3} \cup G_{4}$ 也有一条偶数哈密顿路，因此有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况2： $| F_{1} | = n - 3$

在此条件下，根据引理2.4， $G_{1}$ 有一条哈密顿路 $a_{1} P_{1} b_{1}$ ， $G_{2}$ 有一个哈密顿圈 $C_{2}$ ， $G_{3}$ 有一个哈密顿圈 $C_{3}$ ， $G_{4}$ 有一个哈密顿圈 $C_{4}$ ， $| F - F_{1} | \leq 3$ 。

情况2.1： $P_{1}$ 是偶数阶哈密顿路， $G_{2}$ 是奇图， $G_{3}$ 是奇图， $G_{4}$ 是奇图。

$G_{1}$ 有偶数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有奇数阶哈密顿圈 $C_{4}$ 。显然， $G_{1}$ 有一个完美匹配， $G_{2}$ 有一个几乎完美整数 $k$ -匹配。当 $n \geq 7$ 时，因为 $| E (H_{3}, H_{4}) | = 2^{n - 2} > n$ ，所以 $| E (G_{3}, G_{4}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{3})$ ， $v_{2} \in V (G_{4})$ ，则 $G_{3} \cup G_{4}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{3} v_{1} v_{2} C_{4} {v^{'}}_{2}$ 。所以 $G_{3} \cup G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况2.2： $P_{1}$ 是偶数阶哈密顿路， $G_{2}$ 是偶图， $G_{3}$ 是奇图， $G_{4}$ 是奇图。

$G_{1}$ 有偶数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有奇数阶哈密顿圈 $C_{4}$ 。显然， $G_{1}$ 有一个完美匹配， $G_{2}$ 有一个完美匹配。当 $n \geq 7$ 时，因为 $| E (H_{3}, H_{4}) | = 2^{n - 2} > n$ ，所以 $| E (G_{3}, G_{4}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{3})$ ， $v_{2} \in V (G_{4})$ ，则 $G_{3} \cup G_{4}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{3} v_{1} v_{2} C_{4} {v^{'}}_{2}$ 。所以 $G_{3} \cup G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况2.3： $P_{1}$ 是偶数阶哈密顿路， $G_{2}$ 是奇图， $G_{3}$ 是偶图， $G_{4}$ 是奇图。

$G_{1}$ 有偶数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有奇数阶哈密顿圈 $C_{4}$ 。显然， $G_{1}$ 有一个完美匹配， $G_{3}$ 有一个完美匹配。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{4}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{4}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{2})$ ， $v_{2} \in V (G_{4})$ ，则 $G_{2} \cup G_{4}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{2} v_{1} v_{2} C_{4} {v^{'}}_{2}$ 。所以 $G_{2} \cup G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况2.4： $P_{1}$ 是偶数阶哈密顿路， $G_{2}$ 是偶图， $G_{3}$ 是偶图， $G_{4}$ 是奇图。

$G_{1}$ 有偶数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有奇数阶哈密顿圈 $C_{4}$ 。显然， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况2.5： $P_{1}$ 是偶数阶哈密顿路， $G_{2}$ 是偶图， $G_{3}$ 是偶图， $G_{4}$ 是偶图。

$G_{1}$ 有偶数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G - F$ 有一个完美整数 $k$ -匹配。

情况2.6： $P_{1}$ 是奇数阶哈密顿路， $G_{2}$ 是偶图， $G_{3}$ 是偶图， $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 3$ 。则一定存在某一 $G_{i}$ 如 $G_{2}$ ， $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，所以 $G_{1} \cup {v_{1}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 、 $G_{4}$ 分别有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况2.7： $P_{1}$ 是奇数阶哈密顿路， $G_{2}$ 是奇图， $G_{3}$ 是偶图， $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 3$ 。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 、 $G_{4}$ 分别有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

如果 $\exists v_{2} \in V (G_{3})$ ， $b_{1} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{2}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{3} - {v_{2}}$ 有一个奇数哈密顿圈 ${C^{'}}_{3}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{3}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{3} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{2})$ ， $v_{4} \in V (G_{3}) - {v_{2}}$ ，则 $G_{2} \cup (G_{3} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} C_{2} v_{3} v_{4} {C^{'}}_{3} {v^{'}}_{4}$ 。所以 $G_{2} \cup (G_{3} - {v_{2}})$ 有一个完美匹配。 $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况2.8： $P_{1}$ 是奇数阶哈密顿路， $G_{2}$ 是奇图， $G_{3}$ 是奇图， $G_{4}$ 是偶图。

$G_{1}$ 有奇数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 3$ 。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

如果 $\exists v_{2} \in V (G_{4})$ ， $b_{1} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{2}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{4} - {v_{2}}$ 有一个奇数哈密顿圈 ${C^{'}}_{4}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{4}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{4} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{2})$ ， $v_{4} \in V (G_{4}) - {v_{2}}$ ，则 $G_{2} \cup (G_{4} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} C_{2} v_{3} v_{4} {C^{'}}_{4} {v^{'}}_{4}$ 。所以 $G_{2} \cup (G_{4} - {v_{2}})$ 有一个完美匹配。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况2.9： $P_{1}$ 是奇数阶哈密顿路， $G_{2}$ 是奇图， $G_{3}$ 是奇图， $G_{4}$ 是奇图。

$G_{1}$ 有奇数阶哈密顿路 $P_{1}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 3$ 。则一定存在某一 $G_{i}$ 如 $G_{2}$ ， $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，所以 $G_{1} \cup {v_{1}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有偶数阶哈密顿圈，因此有一个完美匹配。当 $n \geq 7$ 时，因为 $| E (H_{3}, H_{4}) | = 2^{n - 2} > n$ ，所以 $| E (G_{3}, G_{4}) | \geq 1$ 。假设 $v_{2} v_{3} \in E (G - F)$ ， $v_{2} \in V (G_{3})$ ， $v_{3} \in V (G_{4})$ ，则 $G_{3} \cup G_{4}$ 有一条偶数阶哈密顿路 ${v^{'}}_{2} C_{3} v_{2} v_{3} C_{4} {v^{'}}_{3}$ 。所以 $G_{3} \cup G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况3： $| F_{1} | = n - 2$

在此条件下，根据引理2.4， $\exists α \in V (F_{1}) \cup E (F_{1})$ ， $G_{1} + α$ 有一条哈密顿路 $P$ ，所以 $G_{1}$ 由一条路或两条路构成。 $G_{2}$ 有一个哈密顿圈 $C_{2}$ ， $G_{3}$ 有一个哈密顿圈 $C_{3}$ ， $G_{4}$ 有一个哈密顿圈 $C_{4}$ ， $| F - F_{1} | \leq 2$ 。

情况3.1： $G_{1}$ 由一条路构成。

根据情况2，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配或一个几乎完美整数 $k$ -匹配，并且没有孤立点。

情况3.2： $G_{1}$ 由两条路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成。

情况3.2.1： $G_{1}$ 有一个孤立点和一条路。

对任意点 $v_{0} \in V (G_{1})$ ， $H_{1}$ 中存在 $(n - 2)$ 个点 $u_{1}, u_{2}, \dots, u_{n - 2}$ ， $G - H_{1}$ 中存在2个点 $u_{n - 1}, u_{n}$ 与~ $v_{0}$ 相邻。 $H_{1}$ 中存在 $(n - 2)$ 条边 $e_{1}, e_{2}, \dots, e_{n - 2}$ ， $G - H_{1}$ 中存在2条边 $e_{n - 1}, e_{n}$ 以 $v_{0}$ 为端点。当：

$\begin{array}{l} F = {α_{i} | α_{i} \in V (H_{1}) \cup E (H_{1}), i = 1, 2, \dots, n - 2, α_{i} \in V (G - H_{1}) \cup E (G - H_{1}), i = n - 1, n, \\ 当 α_{u}, α_{m} 是两个点时则不相邻, 当 α_{u}, α_{m} 是两条边时则不相交, \\ 当 α_{u}, α_{m} 是一条边一个点时则该点不为该边的端点} \end{array}$

时， $G - F$ 有且仅有一个孤立点 $v_{0}$ 。

情况3.2.2： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 与 $G_{3}$ 是偶图。

$G_{1}$ 由两条偶数阶路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配。

情况3.2.3： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 是偶图， $G_{3}$ 是奇图。

$G_{1}$ 由两条偶数阶路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。显然， $G_{1}$ 、 $G_{2}$ 、 $G_{4}$ 分别有一个完美匹配。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况3.2.4： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 是奇图， $G_{3}$ 是奇图。

$G_{1}$ 由两条偶数阶路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{3}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{3}) | \geq 1$ 。假设 $v_{1} v_{2} \in E (G - F)$ ， $v_{1} \in V (G_{2})$ ， $v_{2} \in V (G_{3})$ ，则 $G_{2} \cup G_{3}$ 有一条偶数阶哈密顿路 ${v^{'}}_{1} C_{2} v_{1} v_{2} C_{3} {v^{'}}_{2}$ 。所以 $G_{2} \cup G_{3}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况3.2.5： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 是偶图， $G_{3}$ 是偶图。

$G_{1}$ 有一条奇数阶路 $a_{1} P_{1} b_{1}$ 与一条偶数阶路 $a_{2} P_{2} b_{2}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 2$ 。则一定存在某一 $G_{i}$ 如 $G_{2}$ ， $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，所以 $G_{1} \cup {v_{1}}$ 有一条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3} \cup G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况3.2.6： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 是奇图， $G_{3}$ 是偶图。

$G_{1}$ 有一条奇数阶路 $a_{1} P_{1} b_{1}$ 与一条偶数阶路 $a_{2} P_{2} b_{2}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 2$ 。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

如果 $\exists v_{2} \in V (G_{3})$ ， $b_{1} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{3} - {v_{2}}$ 有一个奇数哈密顿圈 ${C^{'}}_{3}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{3}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{3} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{2})$ ， $v_{4} \in V (G_{3}) - {v_{2}}$ ，则 $G_{2} \cup (G_{3} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} C_{2} v_{3} v_{4} {C^{'}}_{3} {v^{'}}_{4}$ 。所以 $G_{2} \cup (G_{3} - {v_{2}})$ 有一个完美匹配。 $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况3.2.7： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $G_{2}$ 是奇图， $G_{3}$ 是奇图。

$G_{1}$ 有一条奇数阶路 $a_{1} P_{1} b_{1}$ 与一条偶数阶路 $a_{2} P_{2} b_{2}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 2$ 。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

如果 $\exists v_{2} \in V (G_{4})$ ， $b_{1} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{4} - [v_{2}]$ 有一个奇数哈密顿圈 ${C^{'}}_{4}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{4}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{4} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{2})$ ， $v_{4} \in V (G_{4}) - {v_{2}}$ ，则 $G_{2} \cup (G_{4} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} C_{2} v_{3} v_{4} {C^{'}}_{4} {v^{'}}_{4}$ 。所以 $G_{2} \cup (G_{4} - {v_{2}})$ 有一个完美匹配。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况3.2.8： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $G_{2}$ 是偶图， $G_{3}$ 是偶图。

$G_{1}$ 有两条奇数阶路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点，这八个点各不相同， $| F - F_{1} | \leq 2$ 。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ， $\exists v_{2} \in V (G_{3})$ ， $b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2} v_{2}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个奇数阶哈密顿圈： ${C^{'}}_{2}$ ， $G_{3} - {v_{2}}$ 有一个奇数阶哈密顿圈： ${C^{'}}_{3}$ 。当 $n \geq 7$ 时，因为 $| E (H_{2}, H_{4}) | = 2^{n - 3} > n$ ，所以 $| E (G_{2}, G_{4} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{2}) - {v_{1}}$ ， $v_{4} \in V (G_{3}) - {v_{2}}$ ，则 $(G_{2} - {v_{1}}) \cup (G_{3} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} {C^{'}}_{2} v_{3} v_{4} {C^{'}}_{3} {v^{'}}_{4}$ 。所以 $(G_{2} - {v_{1}}) \cup (G_{3} - {v_{2}})$ 有一个完美匹配。 $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

如果 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况3.2.9： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $G_{2}$ 是奇图， $G_{3}$ 是偶图。

如果 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况3.2.10： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $G_{2}$ 是奇图， $G_{3}$ 是奇图。

如果 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} \cup {v_{1}, v_{2}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

如果 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ， $\exists v_{2} \in V (G_{4})$ ， $b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有两条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2} v_{2}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个偶数哈密顿圈，因此有一个完美匹配， $G_{4} - {v_{2}}$ 有一个奇数阶哈密顿圈 ${C^{'}}_{4}$ 。当 $n \geq 7$ 时，因为 $| E (H_{3}, H_{4}) | = 2^{n - 2} > n$ ，所以 $| E (G_{3}, G_{4} - {v_{2}}) | \geq 1$ 。假设 $v_{3} v_{4} \in E (G - F)$ ， $v_{3} \in V (G_{3})$ ， $v_{4} \in V (G_{4}) - {v_{2}}$ ，则 $G_{3} \cup (G_{4} - {v_{2}})$ 有一条偶数阶哈密顿路 ${v^{'}}_{3} C_{3} v_{3} v_{4} {C^{'}}_{4} {v^{'}}_{4}$ 。所以 $G_{3} \cup (G_{4} - {v_{2}})$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况4： $| F_{1} | = n - 1$

在此条件下，根据引理2.4， $\exists α, β \in V (F_{1}) \cup E (F_{1})$ ， $G_{1} + α + β$ 有一条哈密顿路 $P$ ，所以 $G_{1}$ 由一条路或两条路或三条路构成。 $G_{2}$ 有一个哈密顿圈 $C_{2}$ ， $G_{3}$ 有一个哈密顿圈 $C_{3}$ ， $G_{4}$ 有一个哈密顿圈 $C_{4}$ ， $| F - F_{1} | \leq 1$ 。

情况4.1： $G_{1}$ 由一条路构成。

根据情况2，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配或一个几乎完美整数 $k$ -匹配，并且没有孤立点。

情况4.2： $G_{1}$ 由两条路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成。

根据情况3 (除情况3.2.1)，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配或一个几乎完美整数 $k$ -匹配，并且没有孤立点。根据情况3.2.1， $G - F$ 有且仅有一个孤立点。

情况4.3： $G_{1}$ 由三条路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ 构成。

情况4.3.1： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是偶图。

$G_{1}$ 有三条偶数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况4.3.2： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是奇图。

$G_{1}$ 有三条偶数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有奇数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $G_{3}$ 有一个几乎完美整数 $k$ -匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况4.3.3： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是偶图。

$G_{1}$ 有一条奇数阶路 $a_{1} P_{1} b_{1}$ ，两条偶数阶路 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 1$ 。 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个奇数哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况4.3.4： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是奇图。

$G_{1}$ 有一条奇数阶路 $a_{1} P_{1} b_{1}$ ，两条偶数阶路 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | \leq 1$ 。 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ ， $a_{2} P_{2} b_{2}$ ， $a_{3} P_{3} b_{3}$ 因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况4.3.5： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是偶图。

$G_{1}$ 有两条奇数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ ，一条偶数阶路 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点，这八个点各不相同。 $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $| F - F_{1} | \leq 1$ 。则 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}}$ 有一个偶数阶哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况4.3.6： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $G_{2}$ 是奇图。

$G_{1}$ 有两条奇数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ ，一条偶数阶路 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点，这八个点各不相同。 $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $| F - F_{1} | \leq 1$ 。则 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况4.3.7： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是奇数阶路， $G_{2}$ 是偶图。

$G_{1}$ 有三条奇数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{3}$ 与 $b_{3}$ 在 $T Q_{n}$ 中有四个外邻点，这十二个点各不相同。 $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $a_{3}$ 与 $b_{3}$ 至少有一个点与 $G_{2}$ 相连， $| F - F_{1} | \leq 1$ 。则 $\exists v_{1}, v_{2}, v_{3} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2}, b_{3} v_{3} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3} v_{3}$ ，因此 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}, v_{3}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况4.3.8： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是奇数阶路， $G_{2}$ 是奇图。

$G_{1}$ 有三条奇数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ ， $G_{2}$ 有奇数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{3}$ 与 $b_{3}$ 在 $T Q_{n}$ 中有四个外邻点，这十二个点各不相同。 $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $a_{3}$ 与 $b_{3}$ 至少有一个点与 $G_{2}$ 相连， $| F - F_{1} | \leq 1$ 。则 $\exists v_{1}, v_{2}, v_{3} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2}, b_{3} v_{3} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有三条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{2}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3} v_{3}$ ，因此 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}, v_{3}}$ 有一个偶数阶哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配。 $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况5： $| F_{1} | = n$

在此条件下，根据引理2.4， $\exists α, β, γ \in V (F_{1}) \cup E (F_{1})$ ， $G_{1} + α + β + γ$ 有一条哈密顿路 $P$ ，所以 $G_{1}$ 由一条路或两条路或三条路或四条路构成。 $G_{2}$ 有一个哈密顿圈 $C_{2}$ ， $G_{3}$ 有一个哈密顿圈 $C_{3}$ ， $G_{4}$ 有一个哈密顿圈 $C_{4}$ ， $| F - F_{1} | = 0$ 。

情况5.1： $G_{1}$ 由一条路构成。

根据情况2，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配或一个几乎完美整数 $k$ -匹配，并且没有孤立点。

情况5.2： $G_{1}$ 由两条路 $a_{1} P_{1} b_{1}$ 与 $a_{2} P_{2} b_{2}$ 构成。

情况5.3： $G_{1}$ 由三条路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 与 $a_{3} P_{3} b_{3}$ 构成。

根据情况4，我们可以得到 $G - F$ 有一个完美整数 $k$ -匹配或一个几乎完美整数 $k$ -匹配，并且没有孤立点。

情况5.4： $G_{1}$ 由四条路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ 与 $a_{4} P_{4} b_{4}$ 构成。

情况5.4.1： $a_{1} P_{1} b_{1}$ 是偶数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $a_{4} P_{4} b_{4}$ 是偶数阶路。

$G_{1}$ 有四条偶数阶路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况5.4.2： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是偶数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $a_{4} P_{4} b_{4}$ 是偶数阶路。

$G_{1}$ 有一条奇数路 $a_{1} P_{1} b_{1}$ ，三条偶数阶路 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $| F - F_{1} | = 0$ 。根据 $T Q_{n}$ 的性质， $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连。则 $\exists v_{1} \in V (G_{2})$ ， $b_{1} v_{1} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}}$ 有四条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ，因此 $G_{1} \cup {v_{1}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}}$ 有一个奇数哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况5.4.3： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是偶数阶路， $a_{4} P_{4} b_{4}$ 是偶数阶路。

$G_{1}$ 有两条奇数路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ ，两条偶数阶路 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点，这八个点各不相同， $| F - F_{1} | = 0$ 。根据 $T Q_{n}$ 的性质， $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连。则 $\exists v_{1}, v_{2} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}}$ 有四条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ，因此 $G_{1} \cup {v_{1}, v_{2}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}}$ 有一个偶数哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

情况5.4.4： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是奇数阶路， $a_{4} P_{4} b_{4}$ 是偶数阶路。

$G_{1}$ 有三条奇数路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ ，一条偶数阶路 $a_{4} P_{4} b_{4}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{3}$ 与 $b_{3}$ 在 $T Q_{n}$ 中有四个外邻点，这十二个点各不相同， $| F - F_{1} | = 0$ 。根据 $T Q_{n}$ 的性质， $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $a_{3}$ 与 $b_{3}$ 至少有一个点与 $G_{2}$ 相连。则 $\exists v_{1}, v_{2}, v_{3} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2}, b_{3} v_{3} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有四条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3} v_{3}$ 、 $a_{4} P_{4} b_{4}$ ，因此 $G_{1} \cup {v_{1}, v_{2}, v_{3}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}, v_{3}}$ 有一个奇数阶哈密顿圈，因此有一个几乎完美整数 $k$ -匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个几乎完美整数 $k$ -匹配。

情况5.4.5： $a_{1} P_{1} b_{1}$ 是奇数阶路， $a_{2} P_{2} b_{2}$ 是奇数阶路， $a_{3} P_{3} b_{3}$ 是奇数阶路， $a_{4} P_{4} b_{4}$ 是奇数阶路。

$G_{1}$ 有四条奇数路 $a_{1} P_{1} b_{1}$ 、 $a_{2} P_{2} b_{2}$ 、 $a_{3} P_{3} b_{3}$ 、 $a_{4} P_{4} b_{4}$ ， $G_{2}$ 有偶数阶哈密顿圈 $C_{2}$ ， $G_{3}$ 有偶数阶哈密顿圈 $C_{3}$ ， $G_{4}$ 有偶数阶哈密顿圈 $C_{4}$ 。 $a_{1}$ 与 $b_{1}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{2}$ 与 $b_{2}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{3}$ 与 $b_{3}$ 在 $T Q_{n}$ 中有四个外邻点， $a_{4}$ 与 $b_{4}$ 在 $T Q_{n}$ 中有四个外邻点，这十六个点各不相同， $| F - F_{1} | = 0$ 。根据 $T Q_{n}$ 的性质， $a_{1}$ 与 $b_{1}$ 至少有一个点与 $G_{2}$ 相连， $a_{2}$ 与 $b_{2}$ 至少有一个点与 $G_{2}$ 相连， $a_{3}$ 与 $b_{3}$ 至少有一个点与 $G_{2}$ 相连， $a_{4}$ 与 $b_{4}$ 至少有一个点与 $G_{2}$ 相连，则 $\exists v_{1}, v_{2}, v_{3}, v_{4} \in V (G_{2})$ ， $b_{1} v_{1}, b_{2} v_{2}, b_{3} v_{3}, b_{4} v_{4} \in E (G - F)$ ，则 $G_{1} \cup {v_{1}, v_{2}, v_{3}, v_{4}}$ 有四条偶数阶哈密顿路： $a_{1} P_{1} b_{1} v_{1}$ 、 $a_{2} P_{2} b_{2} v_{2}$ 、 $a_{3} P_{3} b_{3} v_{3}$ 、 $a_{4} P_{4} b_{4} v_{4}$ ，因此 $G_{1} \cup {v_{1}, v_{2}, v_{3}, v_{4}}$ 有一个完美匹配。根据引理2.4， $G_{2} - {v_{1}, v_{2}, v_{3}, v_{4}}$ 有一个偶数阶哈密顿圈，因此有一个完美匹配。 $G_{3}$ 有一个完美匹配， $G_{4}$ 有一个完美匹配。因此， $G - F$ 有一个完美整数 $k$ -匹配。

参考文献

[1]	Cheng, E. and Lipták, L. (2007) Matching Preclusion for Some Interconnection Networks. Networks, 50, 173-180. https://doi.org/10.1002/net.20187
[2]	Cheng, E., Lesniak, L., Lipman, M.J. and Lipták, L. (2008) Matching Preclusion for Alternating Group Graphs and Their Generalizations. International Journal of Foundations of Computer Science, 19, 1413-1437. https://doi.org/10.1142/s0129054108006364
[3]	Cheng, E., Lesniak, L., Lipman, M.J. and Lipták, L. (2009) Conditional Matching Preclusion Sets. Information Sciences, 179, 1092-1101. https://doi.org/10.1016/j.ins.2008.10.029
[4]	Chang, C., Li, X. and Liu, Y. (2023) Integer k-Matching Preclusion of Twisted Cubes and (n, s)-Star Graphs. Applied Mathematics and Computation, 440, Article ID: 127638. https://doi.org/10.1016/j.amc.2022.127638
[5]	Brigham, R.C., Harary, F., Violin, E.C., et al. (2005) Perfect-Matching Preclusion. Congressus Numerantium, 174, Article 42.
[6]	Liu, Y., Su, X. and Xiong, D. (2021) Integer k-Matchings of Graphs: k-Berge-Tutte Formula, k-Factor-Critical Graphs and k-Barriers. Discrete Applied Mathematics, 297, 120-128.
[7]	Liu, Y. and Liu, X. (2018) Integer k-Matchings of Graphs. Discrete Applied Mathematics, 235, 118-128. https://doi.org/10.1016/j.dam.2017.08.013

为你推荐

友情链接