another characterization of line graphs was proven in (and reported earlier without proof by ). he showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an induced subgraph. that is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. in the example above, the four topmost vertices induce a claw (that is, a complete bipartite graph "k"), shown on the top left of the illustration of forbidden subgraphs. therefore, by beineke's characterization, this example cannot be a line graph. for graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.