線圖

圖${\displaystyle G}$ 的線圖${\displaystyle L(G)}$ 定義如下：

• ${\displaystyle L(G)}$ 的一個頂點對應${\displaystyle G}$ 的一邊

• ${\displaystyle L(G)}$ 的頂點相鄰若且唯若它們在${\displaystyle G}$ 對應的邊相鄰（有公共頂點）。

该定义也可以用图论的语言表述如下：设${\displaystyle G=(V,E)}$ ，那么${\displaystyle L(G)=(E,{\tilde {E}})}$ ，且${\displaystyle (e_{1},e_{2})\in {\tilde {E}}\iff e_{1}\cap e_{2}\neq \emptyset }$ 。

下面的例子演示了由原图生成线图的流程。

• 
  原圖
• 
  製作線圖的過程
• 
  結果

由原图转移过来的性质

根据线图的定义，若性质／概念P仅取决于原图${\displaystyle G}$ 中边的邻接性，那么P便可以转移（或者说对偶）到线图${\displaystyle L(G)}$ 上去变成性质／概念P'，刻画线图顶点的邻接属性。例如，图${\displaystyle G}$ 中的一个匹配指的是图中一组不相交的边，把这一概念平移到线图上去，就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。

下面就列举了原图和线图之间的若干联系：

• 若原圖是連通的，線圖也是。
• 若两个图同构，那么它们的线图也同构。
• 若${\displaystyle G}$ 的顶点数和边数分别为${\displaystyle n}$ 和${\displaystyle m}$ ，那么${\displaystyle L(G)}$ 的顶点数和边数分别是${\displaystyle m}$ 和${\textstyle \sum _{v}{\binom {\deg(v)}{2}}}$ 。
• ${\displaystyle \chi _{E}(G)=\chi _{V}(L(G))}$ ，即原圖的邊色數等於線圖的點色數。
• ${\displaystyle G}$ 中的一个匹配对应了${\displaystyle L(G)}$ 中的一个独立集，且其大小相等。于是，${\displaystyle G}$ 中最大匹配的大小等于${\displaystyle L(G)}$ 最大独立集的大小。借助这一关系，可以通过求解后者来求解前者，但反之不总是可行，因为并非所有图都能表示为某个${\displaystyle G}$ 的线图。在计算机科学中，最大匹配问题和最大独立集问题是两个重要的问题。前者已经被高效解决（Edmonds' Blossom Algorithm）；而后者则是NP完全问题，被普遍认为无法高效求解。
• 若${\displaystyle G}$ 存在欧拉回路，则${\displaystyle L(G)}$ 存在哈密顿回路，但反之不然。

惠特尼同构定理

惠特尼同构定理^[1]阐述了以下事实：设有连通图${\displaystyle G_{1}}$ 和${\displaystyle G_{2}}$ 且它们均不是三角形${\displaystyle K_{3}}$ 或爪形${\displaystyle K_{1,3}}$ 。如果${\displaystyle L(G_{1})\cong L(G_{2})}$ ，那么${\displaystyle G_{1}\cong G_{2}}$ 。也就是说，除了极特殊的情形，图${\displaystyle G}$ 的结构可以由线图${\displaystyle L(G)}$ 的结构中唯一地恢复出来。

其它性质

任何的线图都是无爪的，亦即不包含${\displaystyle K_{1,3}}$ 作为导出子图。因此，任意含有偶数个顶点的连通线图都存在完美匹配。

线图${\displaystyle L(G)}$ 的邻接矩阵${\displaystyle A_{m\times m}}$ 的全部特征值都不小于-2。这是因为${\displaystyle A=J^{\operatorname {T} }J-2I}$ ，其中${\displaystyle J_{n\times m}}$ 是原图${\displaystyle G}$ 的关联矩阵（incidence matrix）。又由于矩阵${\displaystyle J^{\operatorname {T} }J}$ 是半正定的，所以${\displaystyle A}$ 的任何特征值${\displaystyle \lambda }$ 均满足${\displaystyle \lambda +2\geq 0}$ 。

Beineke给出了线图的一种等价刻画：${\displaystyle H}$ 是某图的线图当且仅当${\displaystyle H}$ 不包含九种类型的导出子图（见右图）。^[2]

如果${\displaystyle H}$ 的最小度至少为5，那么只有左边一列和右边一列是必要的。换言之，此时，${\displaystyle H}$ 是某图的线图当且仅当${\displaystyle H}$ 不包含六种类型的导出子图（见右图的左边一列和右边一列）。