Šoltés (1994) proved that a connected graph with at least nine vertices is a line graph iff 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 graph iff
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.
