线图

线图将原图中的边变成新图中的顶点。原图的两条边如果共享一个端点，对应的新顶点就相邻。它把“边与边是否接触”的问题转化为普通的顶点邻接问题。

定义与构造

设 $G$ 是有限简单无向图。它的线图记为 $L(G)$，其顶点集是 $E(G)$；对两条不同的原图边 $e,f$，当且仅当它们在 $G$ 中有共同端点时，令它们在线图中相邻。

例如原图是一条四顶点路径 $1-2-3-4$，记三条边为 $e_1=12,e_2=23,e_3=34$。$e_1$ 与 $e_2$ 共享顶点 2，$e_2$ 与 $e_3$ 共享顶点 3，而 $e_1,e_3$ 没有共同端点。因此线图是一条三顶点路径 $e_1-e_2-e_3$。

原图中的三条边分别成为线图的三个顶点。

线图中顶点的度

令 $e=uv$ 为原图的一条边。与它相邻的边包括在 $u$ 处的另外 ${\mathrm{deg}}_G(u)-1$ 条，和在 $v$ 处的另外 ${\mathrm{deg}}_G(v)-1$ 条。由于原图是简单图，这两组不会重合，于是 $${\mathrm{deg}}_{L(G)}(e)={\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)-2.$$ 在上面的路径中，三条边对应的线图顶点度数为 $1,2,1$。如果允许平行边，两组计数可能重合，这个公式需要调整。

两个不同原图

三条边都以中心为端点的星图 $K_{1,3}$，其任意两条边都有公共端点，所以线图是三角形 $K_3$。原图本身若是三角形，其三条边也两两相邻，线图同样是 $K_3$。因此不同的原图可能有相同的线图，不能只凭这个线图断定原图究竟是哪一个。

原图中的孤立顶点不连接任何边，所以不会在线图中产生顶点。若应用中必须保留这些孤立对象，需要在图模型之外另行记录。