Line Graph

A Line Graph $L(G)$ (also called an Interchange Graph) of a graph $G$ is obtained by associating a vertex with each edge of the graph and connecting two vertices with an edge Iff the corresponding edges of $G$ meet at one or both endpoints. In the three examples above, the original graphs are the Complete Graphs $K_3$, $K_4$, and $K_5$ shown in gray, and their line graphs are shown in black.

References

Saaty, T. L. and Kainen, P. C. ``Line Graphs.'' §4-3 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 108-112, 1986.