1. 一条闭途径一定存在一条闭迹（错，$K_2$ 来回可以形成闭途径，但是没有闭迹）

2. 具有 n 个顶点的自补图的个数为 2 个，n 满足 mod 4 = 0， 1

3. 无向图的顶点之间的连通关系一定是等价关系

4. 不含三角形的图都是偶图（错，5 个点的圈）

5. 当n为奇数时，Kn有(n-1)/2条没有公共边的哈密尔顿圈。

存在好算法的是最有匹配问题

• n阶树的点连通度、边连通度为 1

若$G$和$H$是欧拉图，则 $G\times H$ 是欧拉图。

引理1（充要条件） 对于单图$G$，如果$G$中有两个不相邻顶点$u$与$v$，满足：$d\left(u\right)+d\left(v\right)\ge n$ 那么$G$是$H$图当且仅当$G+uv$是$H$图。

引理2 若$G_1$和$G_2$是同一个点集$V$的两个闭图，则$G=G_1\cap G_2$是闭图。（了解即可，不要求掌握）

H 图不能有割边但是可以有割点，比如自环图就存在割点

n 阶完全图中 H 圈的个数为 $(n-1)/2$（n 需要满足为奇数）．

(3) 一个图同构于它的线图，当且仅当它是圈。（相同的点和边进行了交换）

(4) 若图G和$G_1$有同构的线图，则除了一个是$K_3$而另一个是$K_{1,3}$外，$G$和$G_1$同构。(证明比较复杂)

定理3
(1)若G是E图，则L(G) 既是E图又是H图。
(2)若G是H图，则L(G)是H图。

定理4 一个图 $G$ 是 $E$ 图的充要条件是 $L_3(G)$ 为 $H$ 图

定理5 （Chartarand）若$G$ 是$n$个点的非平凡连通图，且不是一条路，则对所有$m\ge n-3，L_m(G)$ 是 $H$ 图。

G 不是 2 连通的，则一定包含割点

---

---

---

有向欧拉图中每个顶点的入度一定等于出度;
有向欧拉图的边集合可以划分为有向圈;

正十二面体是 H 图

---

1.每个 n 方体都有完美匹配, 因为每个 n 方体都是 n 正则偶图，且 $|X|=|Y|$

定理7 一个连通图可2因子分解当且仅当它是偶数度正则图。

定理 7 任一正则偶图是 1-可因子化的。

---

正十二面体是可平面的

(2) $G$是平面图，则 $(G^{\ast }{)}^{\ast }\cong G$ 当且仅当$G$是连通的。(习题第26题)

图G是可平面图当且仅当其每个块是可平面图

若3正则图有割边，则不可1因子分解

一个图的哈密尔顿圈不唯

同构的两个图的度序列相同

若一个图中存在闭途径，则一定存在圈 ❌

若 G 是非连通图，则 A 相似于某个准对角矩阵

回路是边不重圈的并；无回路肯定无圈，加一条边有回路，肯定就有圈

---

---

---

---

图的割点也是子图的割点 ❌ 八字形的图去掉一个块就没有割点

没有割点的非平凡连通图一定是 2 连通图 ❌

---

存在最小度为 3 的 4 连通图 ❌ 最小度为 3，其点连通度最多为 3

非平凡欧拉图中一定有圈

至少具有 2 个点的无环欧拉图一定是 2 边连通的

E 正确：根据 C 选项知欧拉图一定没有割边，所以边连通一定是 2

哈密尔顿图一定没有割点 ❌ 存在自环的哈密尔顿图有割点；哈密尔顿简单图中一定不存在割点

---

---

---

---

---

---

---

---

---

三正则哈密尔顿图存在完美匹配

---

图 G 的一个完美匹配实际上就是它的一个 1 因子

图 G 的一个 2-因子实际上就是它的一个哈密尔顿圈 ❌

非平凡树可以 1-因子分解 ❌，可以 1-因子分解的图一定是偶数阶数的正则图

可 1-因子分解的 3 正则图一定是哈密尔顿图 ❌

D. 若图 G 是 2k 正则连通图，则 可以分解为 k 个二因子的并

---

---

---

---

---

---

---

---

---