Šoltés (1994) proved that a connected graph with at least nine vertices is a line graphiff it does not contain any of seven given graphs as a forbidden
induced subgraph, and furthermore that the number seven cannot be reduced even
if the number of vertices is increased.

Šoltés (1994) labels the Beineke graphs as illustrated above and notes that these forbidden subgraphs have different roles
in Beineke's characterization of line graphs (Beineke 1968). In particular, if the
one of the graphs - is omitted, the class of graphs having
the remaining graphs as forbidden subgraphs will contain infinitely many connected
graphs which are not line graphs. On the other hand, omitting both graphs and yields a class containing only five connected non-line graphs.

Šoltés (1994) then establishes that a graph is a line graphiff

1. it does not contain any of the graphs -
as an induced subgraph and is not ,

2. it does not contain any of the graphs -
and
as an induced subgraph and is neither nor , or

3. it does not contain any of the graphs -
as an induced subgraph and is not isomorphic to any of the graphs , , , , and .

Finally, Šoltés (1994) shows that each of the five graph illustrated above contains exactly one of the graphs as an induced subgraph. Note that
in the case of ,
an edge across the diamond that was omitted in the published paper has been added.

Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and
H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.Šoltés,
Ľ. "Forbidden Induced Subgraphs for Line Graphs." Disc. Math.132,
391-394, 1994.