A Line Graph (also called an Interchange Graph) of a graph is obtained by associating a vertex with each edge of the graph and connecting two vertices with an edge Iff the corresponding edges of meet at one or both endpoints. In the three examples above, the original graphs are the Complete Graphs , , and 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.

© 1996-9

1999-05-25