Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem (Q1766108)

An early observation that line graphs have least eigenvalue greater than or equal to \(-2\) led to the natural problem to characterize the graphs with this property. Such graphs turned out to be generalized line graphs and a few hundreds of exceptional graphs [see \textit{P. J. Cameron, J. M. Goethals, J. J. Seidel} and \textit{E. E. Shult}, J. Algebra 43, 305--327 (1976; Zbl 0337.05142)]. Generalized line graphs were later characterized by a collection of 31 forbidden induced subgraphs in [\textit{D. Cvetković, M. Doob} and \textit{S. Simić}, J. Graph Theory 5, 385-399 (1981; Zbl 0475.05061)], and independently by \textit{S. B. Rao} et al. [Proc. Symp., Calcutta 1980, Lect. Notes Math. 885, 459--472 (1981; Zbl 0494.05053)]. However, the existing proofs of this result are rather involved. The paper under review provides a new proof by introducing an edge-colouring technique for investigating minimal non-generalized line graphs. It is then shown that such a graph has at most 8 vertices.