无爪图的1-因子问题
此文源自 于青林和刘桂真的 图的因子和匹配可扩性问题。并做适当的补充。
如果一个图不包含 K_{1,3} 作为导出子图就称其为无爪的(claw free). 无爪图是研究图参数一个非常常见的条件。一个重要的原因是因为无爪条件下，很多图论问题变得简单起来。比如我们之前提到确定任意图的最大独立集的问题是NP困难的，但是加上无爪的限制条件就惊人的变成了P问题。在极值图论中也经常作为条件进行讨论。这篇文章讨论无爪图的1因子问题。
定理 [Sumner] 若 G 是连通的偶阶无爪图，那么它含 1 -因子。
证明: 对于 |G| 做数学归纳法，假设 P=v_1,v_2,\cdots,v_l 是 G 的最长路，那么 k\ge 3 ,且 N_G(v_1)\subseteq V(P)-\{v_1\} 。
论断: G-\{v_1,v_2\} 是连通的。
如果 d_G(v_2)=2 , 由于 N_G(v_1)\subseteq V(P)-\{v_1\}， 那么 G\setminus \{v_1,v_2\} 是连通的。如果 d_G(v_2)=3 ，对于每个 x\in N_G(v_2)-V(P) , xv_3 一定是 G 的一条边。否则因为 x.v_1,v_2,v_3 不能导出一个爪，所以 v_1x 或者 v_1v_3 一定是 G 的一条边，然后两种情况均会导致找到比 P更长的路，矛盾。因此 G-\{v_1,v_2\} 也是连通的，也是无瓜的。且的偶数阶的， G-\{v_1,v_2\} 有 1 -因子，所以 G 也有 1 -因子。
上次文章提到任意一个图的线图是无爪的(从定义可分析）故而都是线图含1因子的。
关于一些顶点数较少的无爪图如下所示:
The numbers of claw-free simple graphs on nodes for n=1,2 , ... are 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (OEISA086991; illustrated above).
