In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L that represents the adjacencies between edges of G. L is constructed in the following way: for each edge in G, make a vertex in L; for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L. Wikipedia