Š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 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 graphs 
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.
