Line graph

Summary

The line graph $L(G)$ of a graph $G$ has the edges of $G$ as its vertices. Two of them are adjacent when they share an endpoint. It turns questions about edges into questions about vertices. For example, a matching of $G$ is an independent set of $L(G)$, and an edge colouring of $G$ is a vertex colouring of $L(G)$. The node line graph gives the precise definition.