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; 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).