Let be a graph. The line graph of is denoted by and is defined as follows. The vertices of are the edges of . Two vertices of are connected by an edge if and only if the corresponding edges in form a path (which must be a directed path if is a digraph).
Let be the undirected graph on the vertex set and edge set . Then the line graph has vertex set . Since and are incident in , they are connected by an edge in . We label this edge by the unique walk from to determined by these edges, namely . With this notation, the edge set is .
Above we display the graphs (left) and (right).
Part of the reason for interest in line graphs is the following observation:
If a graph is Eulerian, then its line graph is Hamiltonian.
This follows immediately from the fact that a sequence of incident edges in is a sequence of incident vertices in .
Let be the de Bruijn digraph on binary strings of length . Then for , the next de Bruijn digraph can be obtained by taking the line graph of the previous one, that is, .