# Why line graph is a proper subclass of claw-free graph?

A claw is the graph isomorphic to $K_{1,3}$, that is, a star graph with three edges, three leaves, and one central vertex. (see below)

A graph is claw-free if it does not contain a claw as an induced subgraph.

The line graph of G is the intersection graph of the edges of G, that represents the adjacencies between edges of G.

A graph $F$ is a line graph if there exists a graph $H$ such that $L(H) = F$.

My question is why are line graphs a subclass of claw-free graphs?? Thanks a lot!

• What have you tried? Have you tried to find a graph $H$ such that $L(H) = K_{1,3}$? There are only so many possibilities for $H$, so you should be able to try them all. What happens when you do that?
– D.W.
Apr 10 '18 at 0:02
• I'm confused. Even the line graph in the picture shown contains claws. Apr 10 '18 at 0:14
• @Billiska "Claw-free" means no induced subgraphs are claws. I've edited to correct the definition in the question. Apr 10 '18 at 0:25
• oh. never mind. induced by vertex. not induced by edge. Yes, I was going insane. thanks. Apr 10 '18 at 1:07
• "why the former is proper subclass ". This is a different question from the one you asked originally. Please create a new question if you want to know something other than your original question. Thanks. Apr 10 '18 at 9:20

"Line graphs may be characterized in terms of nine forbidden subgraphs;[2] the claw is the simplest of these nine graphs."

The reference is to the following paper:

[2] Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.

Wikipedia contains a pictorial description of these nine graphs. One of them is $K_5^-$, obtained from $K_5$ by removing a single edge.

If you take any of the other forbidden subgraphs then you get a claw-free graph which isn't a line graph.

• Thank you very much. Wow, I am a slow learner, it takes me time to understand the answer...:-) I am now working on it..... Apr 11 '18 at 17:04