Line graph

Remarks

If $e = uv$ is an edge of $G$, its degree in $L(G)$ is $\deg u + \deg v - 2$. Example: the cycle graph $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}$.