Editing Line graph (section)

===Other related graph families===
All line graphs are [[claw-free graph]]s, graphs without an [[induced subgraph]] in the form of a three-leaf tree.<ref name="h72-8.4"/> As with claw-free graphs more generally, every connected line graph {{math|''L''(''G'')}} with an even number of edges has a [[perfect matching]];<ref>{{Citation
 | last = Sumner | first = David P.
 | doi = 10.2307/2039666
 | mr = 0323648
 | journal = Proceedings of the American Mathematical Society
 | pages = 8–12
 | title = Graphs with 1-factors
 | volume = 42
 | year = 1974
 | issue = 1
 | publisher = American Mathematical Society
 | jstor = 2039666
}}. {{Citation
 | last = Las Vergnas | first = M. | author-link = Michel Las Vergnas
 | mr = 0412042
 | issue = 2–3–4
 | journal = Cahiers du Centre d'Études de Recherche Opérationnelle
 | pages = 257–260
 | title = A note on matchings in graphs
 | volume = 17
 | year = 1975
}}.</ref> equivalently, this means that if the underlying graph {{mvar|G}} has an even number of edges, its edges can be partitioned into two-edge paths.

The line graphs of [[tree (graph theory)|tree]]s are exactly the claw-free [[block graph]]s.<ref>{{harvtxt|Harary|1972}}, Theorem 8.5, p.&nbsp;78. Harary credits the result to [[Gary Chartrand]].</ref> These graphs have been used to solve a problem in [[extremal graph theory]], of constructing a graph with a given number of edges and vertices whose largest tree [[induced subgraph|induced as a subgraph]] is as small as possible.<ref>{{citation
 | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
 | last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician)
 | last3 = Sós | first3 = Vera T. | author3-link = Vera T. Sós
 | doi = 10.1016/0095-8956(86)90028-6
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 61–79
 | title = Maximum induced trees in graphs
 | volume = 41
 | year = 1986| doi-access = free
}}.</ref>

All [[eigenvalue]]s of the [[adjacency matrix]] {{mvar|A}} of a line graph are at least −2. The reason for this is that {{mvar|A}} can be written as <math>A = J^\mathsf{T}J - 2I</math>, where {{mvar|J}} is the signless incidence matrix of the pre-line graph and {{mvar|I}} is the identity. In particular, {{math|''A'' + 2''I''}} is the [[Gramian matrix]] of a system of vectors: all graphs with this property have been called generalized line graphs.{{sfnp|Cvetković|Rowlinson|Simić|2004}}