I understand the definition of a line graph as: The line graph of a graph $G$ has vertex set $E(G)$ with two vertices being adjacent if and only if the corresponding edges of $G$ share a vertex. In a claw there are three edges and 4 vertices and in the line graph there are still 3 edges but only 3 vertices, is this why it is not a line graph?


You are right that the claw is not its own line graph, because as you mentioned there are not enough vertices. However, what they're asking about is something stronger. They are asking you to prove that there is no graph for which the claw is the line graph.

You can prove this, for instance by contradiction. If there were such a graph, it would have to have four edges (since the claw has four vertices). One of the edges will share a vertex with each of the other three, but none of those other three will have any vertices in common. This is actually impossible, and you should draw figures and come up with a good reason for why it is impossible.

Then if this is homework or an assignment or something like that, you should write a small text that will convince whoever is correcting it that you have indeed understood why the claw is not a line graph, and that is what you should hand in. If this is not the case, then you can ignore this paragraph.

  • $\begingroup$ Thanks that makes sense. $\endgroup$ – user528681 Feb 6 '18 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.