A simple graph is a line graph of some simple graphiff
if does not contain any of the above nine graphs, known in this work as Beineke graphs,
as a forbidden induced subgraph (van
Rooij and Wilf 1965; Beineke 1968; Beineke 1970; Skiena 1990, p. 138; Harary
1994, pp. 74-75; West 2000, p. 282; Gross and Yellen 2006, p. 405).
This statement is sometimes known as the Beineke theorem. These nine graphs are implemented
in the Wolfram Language as GraphData["Beineke"].
Of the nine, one has four nodes (the claw graph = star graph = complete bipartite
graph),
two have five nodes, and six have six nodes (including the wheel
graph).
= complete bipartite
graph 
),
two have five nodes, and six have six nodes (including the wheel
graph 
).
