# Triangle-free Graphs

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?

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.

• Isn't the line graph of your example something that looks like a V (rather than a triangle)? – anonymous Mar 20 '17 at 10:40
• @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). – Henning Makholm Mar 20 '17 at 10:45
• Oh right! Sorry, I made a mistake and thought of something else. Thanks. – anonymous Mar 20 '17 at 10:48