⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.28 2022
本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。
目录
有特定需要的内容直接跳转到相关章节查看即可。
超哈密尔顿图和迹
超哈密尔顿图
若图 $G$ 是非 $H$ 图, 但对于 $G$ 中任意点 $v$，都有 $G−v$ 是 $H$ 图，则称 $G$ 是
下面有一个定理:
证明:
证明 Peterson 图不是 $H$ 图的过程略。
下面基于已知 Peterson 图不是 $H$ 图的结论，证明 Peterson 图是超 $H$ 图。
由对称性可知，只需考虑 $G-v_1$ 的情形即可。如上图所示即是删去 $v_1$ 之后的图中存在的 $H$ 圈。因此，Peterson 图是超 $H$ 图。
超哈密尔顿迹的概念
图 $G$ 称为是
若 $G$ 中没有 $H$ 路，但是对 $G$ 中任意点 $v$，$G−v$ 存在 $H$ 路，则称 $G$ 是
欧拉图和哈密尔顿图的关系
如下所示，$E$ 图和 $H$ 图之间似乎并不存在关系:
本节将说明欧拉图和哈密尔顿图之间的关系。
线图的定义
设 $G$ 是图，$G$ 的线图 $L(G)$ 定义为:
$(e_1,e_2) \in E(L(G)) \Leftrightarrow$ 在 $G$ 中有 $e_1$ 与 $e_2$ 邻接
上述定义的含义是，将 $G$ 中的各条边转换为 $L(G)$ 中的点。如果 $G$ 的两条边在 $G$ 中相邻，则它们所对应的点在 $L(G)$ 中相邻。
再给出一个定义: $G$ 的
线图的性质
线图有如下性质:
- 线图 $L(G)$ 顶点数等于 $G$ 的边数，若 $e=uv$ 是 $G$ 的边，则 $e$ 作为 $L(G)$ 的顶点度数为: $d(e)=d(u)+d(v)−2$;
- 若 $G=(n,m)$，则线图 $L(G)$ 的边数为: $$m[L(G)]=-m+\frac{1}{2}\sum_{v \in V(G)}d^2(v)$$
(1) 显然，下面对 (2) 使用两种方法进行证明:
证法 1: 由线图 $L(G)$ 有 $m$ 个顶点，则对于 $G$ 中任一顶点 $v$，关联于该顶点的 $d(v)$ 条边将产生 $L(G)$ 中 $C_{d(v)}^{2}$ 条边 (i.e. 任两条边在 $L(G)$ 代表的点都是邻接的)，所以 $L(G)$ 中的总边数为: $$m[L(G)] = \sum_{v \in V(G)}C^2_{d(v)} = \frac{1}{2} \sum_{v \in V(G)} d(v) \cdot [d(v)-1] = -m + \frac{1}{2} \sum_{v \in V(G)} d^2(v)$$
证法 2: 对线图使用握手定理，可得: $$m[L(G)] = \frac{1}{2} \sum_{uv \in E(G)} d_{L(G)}(uv) = \frac{1}{2} \sum_{uv \in E(G)} (d_G(u) + d_G(v) - 2) = \frac{1}{2} \sum_{uv \in E(G)}(d_G(u)+d_G(v)) - \frac{1}{2} \cdot 2|E(G)| = -m + \frac{1}{2} d_G^2(w) $$
另外，有结论:
另外：
剖分图
图 $G$ 的
如果我们定义 $L_n(G)=L(S_{n-1}(G))$ (p.s. 注意和 $L^n(G)$ 区分)，则我们有:
$E$ 图和 $H$ 图的关系
有如下关系:
值得注意的是，上述定理的逆不成立。
基于上述定理，定义图 $G$ 的