2
$\begingroup$

I'm confused about how you to recognize line graphs.

From the Wikipedia page on the subject, I read that

A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph:

Forbidden line subgraphs

Which explains why this graph is not a line graph as it induces a claw, which is one of the forbidden subgraph.

enter image description here

However here's a graph and its subgraph (in green). This line graph also contains a claw, if you look at the vertex (4,3) which is adjacent to (1,3), (1,4) and (4,5).

a graph G it's line graph

What am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

When we say induced subgraph, we mean you choose some vertices and take all edges between them. So when you choose (4,3), (1,3), (1,4), and (4,5) you get a diamond (with an edge across its middle), not the claw.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .