The term "Beineke graphs" is used in this work for the nine graphs illustrated above. A simple graph is a line
graph of some simple graphiff
it contains none of the 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 
).
