Hamilton图.md
含有Hamilton回路的图是Hamilton图
显然，$n$个点的完全图是Hamilton图
必要条件
- 没有点度数为0（哪来的路）
- 没有点度数为1（压根构不成回路）
- 度数为2的点两条边均出现在回路中（毕竟是回路）
- 度数大于2的点只选两条边（多了就重复经过点了）
- 删去任意数量点后的连通分支数$\le$删去点的个数（因为有回路，删掉一个点还是连通的，之后每删一个点最多只能增加一个连通分支）
充分条件
-
点数$\ge 3$，而且点的最小度数$\ge$点数$/2$
证明“不是Hamilton图”推出“存在点度数$<$点数$/2$”即可。 对于任意非Hamilton图，把它扩成极大非Hamilton图，度数只增不减，因此证极大非Hamilton图存在点度数$\lt$点数$/2$即可。
极大非Hamilton图必定存在不相邻的两点$u$和$v$，这两点之间必定存在Hamilton通路，将它看成一个序列，其中相邻于$u$的点的前一个点放进集合$S$，相邻于$v$的点放进集合$T$，显然$S$中点的个数等于$u$的度数，$T$中点的个数等于$v$的度数，而且$v$不属于这两个集合，也可证出$S\cap T=\emptyset$（如果交集非空可推出存在欧拉回路），于是$u$的度数$+v$的度数$\lt$总的点数，必有一个度数$\lt$点数$/2$
-
闭合图是完全图（由充要条件第二条，再加上完全图是Hamilton图显然）
-
对于不减度序列$(d_1,d_2,\cdots,d_n)(n\ge 3)$，不存在$m\le n/2$使得 $$d_m\le m, d_{n-m}\lt n-m$$
只需证明闭合图是完全图即可。
利用反证法，我们先假设闭合图不是完全图
选取闭合图中度数之和最大的两个不相邻的点$u$和$v$。不妨假设$u$在闭合图中的度数小于$v$在闭合图中的度数，因为这两个点在闭合图中不相邻，所以根据闭合图的性质，他们俩的在闭合图中的度数之和小于点数。
我们把闭合图中和$v$不相邻的点放进集合$S$，和$u$不相邻的点放进集合$T$，显然$S$包含$(n-v在闭合图中的度数)$个点，$T$包含$(n-u在闭合图中的度数)$个点
显然$u,v$均在$S,T$里，而我们取的时候是取度数之和最大的不相邻的两个点，所以，$S-\{v\}$中度数最大的点是$u$，$T$中度数最大的点是$v$，于是
$$ \begin{align} (闭合图中度数\le u的度数的点的数量)&\ge |S|-1\\ &=点数-v在闭合图中的度数-1\\ &\gt点数-(点数-u在闭合图中的度数)-1\\ &=u在闭合图中的度数-1 \end{align} $$
于是，闭合图中至少有$d'(u)$个点的度数小于$d'(u)$
类似地
$$ \begin{align} (闭合图中度数\le v的度数的点的数量)&\ge |T|\\ &=点数-u在闭合图中的度数\\ \end{align} $$
于是，闭合图中至少有$n-d'(u)$个点的度数小于$d'(v)$，也就可能有更多的点度数小于$n-d'(u)(\ge d'(v))$
于是，取$m=d'(u)$，能够满足起初的两个条件，也就是存在这样的$m$，发生了矛盾，于是该闭合图必然是完全图
充要条件
-
在存在不相邻两点$u$和$v$度数之和$\ge$点数的前提下，加上边$uv$后是Hamilton图是该图为Hamilton图的充要条件
必要性显然。对于充分性，如果不是Hamilton图，则按照上面对第一个充分条件的证明中的结论，$u$和$v$的度数之和$\lt$点数，矛盾
-
闭合图是Hamilton图
在这个图闭合图是本身的情况下显然。否则，就满足了上一条充要条件的前提，于是可以根据上一条构造一条等价链，从而得证
证否充分条件
-
$C_{m,n}$是非Hamilton图
去掉中间那部分$K_m$的$m$个点之后，连通分支个数为$m+1\gt m$，不满足上面必要条件的第5项，因此是非Hamilton图
证否必要条件
-
若图是含$n$个点的非Hamilton图，则这个图是由某个$C_{m,n}$度增大形成
设图的不减度序列为$(d_1,d_2,\cdots,d_n)$，由充分条件的第3条可知，存在$m\lt n/2$使得$d_m\le m$且$d_{n-m}\lt n-m$
所以原序列被
$$ (m,\cdots,m(m个),n-m-1,\cdots,n-m-1(n-2m个),n-1,\cdots,n-1(m个)) $$
度增大
显然这个度序列是$C_{m,n}$的度序列，因此得证