---
tag: CJ57DT86S8
kind: definition
name: Line graph
msc: [05C76]
defines: GTN3QQYTT5
uses: [0JD5C82QMB, 0WNGQBPPQX]
sources:
  - url: https://en.wikipedia.org/wiki/Line_graph
---

## Definition

Let $G = (V, E)$ be a [[graph|0JD5C82QMB]].
The line graph of $G$ is the graph $L(G)$ whose vertex set is the [[edge set|0WNGQBPPQX]] $E$ of $G$.
Two distinct edges $e, f \in E$ are adjacent in $L(G)$ if and only if they have a common endpoint.

## Remarks

If $e = uv$ is an edge of $G$, its degree in $L(G)$ is $\deg u + \deg v - 2$.
Example: the [[cycle graph|0QQ0F12962]] $C_n$ with $n \ge 3$ has $L(C_n) \cong C_n$, since each edge meets exactly the two edges next to it around the cycle.
Also $L(K_{1,3}) \cong K_3$: the three edges of the star share the centre, so they are pairwise adjacent.
Non-example: the star $K_{1,3}$ is itself not the line graph of any graph.
Indeed, suppose a vertex $e$ of $L(H)$ had three pairwise non-adjacent neighbours.
These would be three edges meeting $e$, so two of them would meet $e$ at the same endpoint, and these two would be adjacent.
Whitney showed that two connected graphs with isomorphic line graphs are isomorphic, except for the pair $K_3$ and $K_{1,3}$.