In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both
and used the
construction before this.
Other terms used for the line graph include edge graph,
the theta-obrazom, the covering graph,
the derivative, the edge-to-vertex dual, the
interchange graph, the adjoint graph, the
conjugate, the derived graph, and the
representative graph.

One of the earliest and most important theorems about line graphs is due to , who proved that with one exceptional case the structure of G can be recovered completely from its line graph.