PROBLEM
Prove that a line graph is claw-free.
PROOF
Let $G$ be a simple graph and denote $L(G)$ as it's line graph. We aim to show that $L(G)$ must be claw-free, where a claw is $K_{1,3}$, the complete bipartite graph where one partition has one vertex and the other partition has three vertices. Assume by way of contradiction that $L(G)$ does contain a claw. That would imply that there exists $e_1, e_2, e_3, e_4\in E(G)$ so that, without loss of generality, $e_1, e_2, e_3$ must all share an endpoint with $e_4$. But, $L(G)$ having a claw implied that $e_1,e_2,e_3,e_4$ only shared three common vertices. (that is, the common vertex of $e_4$ and $e_i$ is $v_i$,which is unique, so
we have at most $3$ such vertices. On the other hand, since $e_4$ has only $2$ vertices, two of these must be the same.)
Thus by the pigeonhole principle, it must be that at least two of $e_1,e_2,e_3$ are adjacent. This a contradiction. Thus $L(G)$ must be claw-free.
Prove that a line graph is claw-free.
PROOF
Let $G$ be a simple graph and denote $L(G)$ as it's line graph. We aim to show that $L(G)$ must be claw-free, where a claw is $K_{1,3}$, the complete bipartite graph where one partition has one vertex and the other partition has three vertices. Assume by way of contradiction that $L(G)$ does contain a claw. That would imply that there exists $e_1, e_2, e_3, e_4\in E(G)$ so that, without loss of generality, $e_1, e_2, e_3$ must all share an endpoint with $e_4$. But, $L(G)$ having a claw implied that $e_1,e_2,e_3,e_4$ only shared three common vertices. (that is, the common vertex of $e_4$ and $e_i$ is $v_i$,which is unique, so
we have at most $3$ such vertices. On the other hand, since $e_4$ has only $2$ vertices, two of these must be the same.)
Thus by the pigeonhole principle, it must be that at least two of $e_1,e_2,e_3$ are adjacent. This a contradiction. Thus $L(G)$ must be claw-free.
No comments:
Post a Comment