为什么爪图$K_{1,3}$不是线图？

嘿，咱们先把问题里的概念和逻辑理清楚，别搞混啦！

首先，你对线图的定义理解完全正确：图$G$的线图$L(G)$以$G$的边集$E(G)$为顶点集，两个顶点相邻当且仅当原图中对应的两条边共享一个公共顶点。

接下来咱们拆解你的疑问：

• 爪图（也就是完全二分图$K_{1,3}$）确实是4个顶点、3条边的结构：1个中心顶点连接3个叶子顶点。
• 爪图的线图$L(K_{1,3})$是什么样的？因为爪图的3条边两两都共享中心顶点，所以线图里的3个顶点（对应爪图的3条边）两两相邻，这就是完全图$K_3$——3个顶点、3条边，完全符合线图的构造规则。

然后重点来了：你问“这是它不是线图的原因吗？”这里的“它”应该指的是爪图本身吧？如果是这样，那你的猜测是不对的，原因和顶点数/边数的变化没关系，核心原因是：
爪图$K_{1,3}$本身无法成为任何一个图的线图。咱们可以用反证法理解：假设存在某个图$G$，使得$L(G)=K_{1,3}$，那$L(G)$的4个顶点对应$G$的4条边。$K_{1,3}$里有1个度数为3的中心顶点，它对应$G$中的某条边$e$，这条边需要和另外3条边都相邻（也就是共享顶点），那$e$的至少一个端点得是另外3条边的公共顶点，这样那3条边在$L(G)$里应该两两相邻，但$K_{1,3}$的3个“叶子”顶点之间是不相邻的，这就矛盾了！所以不存在这样的$G$，因此爪图不是线图。

另外补充一下，判断一个图是不是线图有专门的Beineke定理，它列出了9个禁止子图，爪图就是其中之一——只要图里包含爪图作为子图，那它就不可能是线图。

而你提到的爪图的线图（也就是$K_3$），它本身是线图哦，比如完全图$K_3$的线图就是它自己。

内容的提问来源于stack exchange，提问作者user528681