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. An example graph (black) and its corresponding line graph (red) are illustrated above.

Line graphs are implemented as LineGraph[g] in the Mathematica package Combinatorica`) . Precomputed line graph identifications of many named graphs can be obtained in Mathematica using GraphData[graph, "LineGraphName"].

Taking the line graph twice does not return the original graph unless the line graph of a graph is isomorphic to itself. In fact, The only connected graph that is isomorphic to its line graph is a cycle graph for (Skiena 1990, p. 137). The numbers of not-necessarily connected simple graphs that are isomorphic to their lines graphs for , 2, ... are 0, 0, 1, 1, 1, 2, 2, 3, 4, ..., illustrated above.

The following table summarizes some named graphs and their corresponding line graphs.

claw graph	triangle graph
complete bipartite graph	prism graph
cubical graph	cuboctahedral graph
cycle graph	cycle graph
dodecahedral graph	icosidodecahedral graph
path graph	singleton graph
path graph	path graph
square graph	square graph
star graph	tetrahedral graph
star graph	pentatope graph
star graph	complete graph
tetrahedral graph	octahedral graph
triangle graph	triangle graph

The line graph of a graph with nodes, edges, and vertex degrees contains nodes and

edges (Skiena 1990, p. 137). The incidence matrix of a graph and adjacency matrix of its line graph are related by

where is the identity matrix (Skiena 1990, p. 136).

A graph is a line graph iff if does not contain any of the above nine graphs as an induced subgraph (van Rooij and Wilf 1965; Beineke 1968; Skiena 1990, p. 138). These nine graphs are implemented in Mathematica as GraphData["NonLineSubgraph"]. Of the nine, one has four nodes (the claw graph = star graph = complete bipartite graph ), two have five nodes, and six have six nodes (including the wheel graph ).

Whitney (1932) showed that, with the exception of and , any two connected graphs with isomorphic line graphs are isomorphic (Skiena 1990, p. 138).

The line graph of an Eulerian graph is both Eulerian and Hamiltonian (Skiena 1990, p. 138). More information about cycles of line graphs is given by Harary and Nash-Williams (1965) and Chartrand (1968).

Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.

Chartrand, G. "On Hamiltonian Line Graphs." Trans. Amer. Math. Soc. 134, 559-566, 1968.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Harary, F. and Nash-Williams, C. J. A. "On Eulerian and Hamiltonian Graphs and Line Graphs." Canad. Math. Bull. 8, 701-709, 1965.

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.

Skiena, S. "Line Graph." §4.1.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 128 and 135-139, 1990.

van Rooij, A. and Wilf, H. "The Interchange Graph of a Finite Graph." Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965.

Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

CITE THIS AS:

Weisstein, Eric W. "Line Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/LineGraph.html