A simple graph is a line graph of some simple graph iff 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 ).
A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the six Metelsky graphs as a forbidden induced subgraph (Metelsky and Tyshkevich 1997).