Line graph

In graph theory, the line graph L(G) of a graph G is a graph such that

each vertex of L(G) represents an edge of G; and
any two vertices of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common endvertex, in G.

A line graph L(G) can easily be constructed from any graph by

. Create a vertex in L(G) for each edge of G
. For each vertex in L(G), add an edge to all of its neighbors — all the other vertices corresponding to edges in G that touch the vertex at either end of the edge in G.

Some graphs are not a line graph. For example, the graph

    *
    |
    |
 *--*--*
  \ | /
   \|/
    *

is not a line graph of any other graph.

The line graph of the above graph is

     *
    /|\
   / | \
  *--|--*
  |\ | /|
  | \|/ |
  |  *  | 
  | / \ |
  |/   \|
  *-----*

Properties

The line graph of a connected graph is connected
<math>\chi_E(G) = \chi_V(L(G))<math>, the edge chromatic number of a graph is equal to the vertex chromatic number of its line graph