1
$\begingroup$

Is it possible to have triangles in the line graphs of triangle free graphs? I drew some examples for n=1,2,3,4, and 5 but I don't see any triangles yet.

And what is the explanation behind it if there are or aren't triangles?

$\endgroup$
2
$\begingroup$

Sure -- if the original graph has a vertex of degree 3, then there will be a triangle in the line graph.

The smallest example would be

      O
     /
O---O
     \
      O

whose line graph is a triangle.

Or, for a bridgeless example, consider the cube graph.

$\endgroup$
  • $\begingroup$ Isn't the line graph of your example something that looks like a V (rather than a triangle)? $\endgroup$ – anonymous Mar 20 '17 at 10:40
  • $\begingroup$ @anonymous: No, the line graph has one vertex for each edge in the claw graph, and any two vertices in it are neighbors (because any two edges in the claw share a vertex). $\endgroup$ – Henning Makholm Mar 20 '17 at 10:45
  • $\begingroup$ Oh right! Sorry, I made a mistake and thought of something else. Thanks. $\endgroup$ – anonymous Mar 20 '17 at 10:48

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.