Editing Line graph (section)

===Forbidden subgraphs===
[[File:Forbidden line subgraphs.svg|thumb|300px|The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.]]
Another characterization of line graphs was proven in {{harvtxt|Beineke|1970}} (and reported earlier without proof by {{harvtxt|Beineke|1968}}). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an [[induced subgraph]]. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a [[complete bipartite graph]] {{math|''K''{{sub|1,3}}}}), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.<ref name="mt97">{{harvtxt|Metelsky|Tyshkevich|1997}}</ref>