弦图

弦图是每个长度至少为四的环都有一条弦的简单无向图。环的弦连接环上两个不相邻的顶点；它把较长的环切成两个较短的环。这里考察有限图。

从四顶点环开始

四顶点环 $1-2-3-4-1$ 没有对角线，因此有一个长度为四、没有弦的环，不是弦图。增加边 $13$ 后，原来的四环被这条弦切成三角形 $123$ 与 $134$；这个四顶点图中所有长度至少为四的环都有弦，故是弦图。

左侧四环没有弦；右侧边 13 是四环的一条弦。

长度为三的环无需有弦：三角形中的每一对顶点原本已经沿环相邻。树不含任何环，因此按定义也是弦图。

等价的诱导子图描述

一个环如果没有弦，那么取该环全部顶点的诱导子图时，所得边恰是环边；这称为诱导环。反过来，长度至少四的诱导环不可能有弦，因为弦若存在也必须出现在诱导子图里。因此，下列说法等价：

• 图是弦图。
• 图没有长度至少为四的诱导环。

这里“诱导”不可省略。弦图当然可以包含长度为四的环；只要该环有对角线，它就不构成无弦的诱导四环。

消去顶点

如果一个顶点的所有邻居两两相邻，称该顶点为单纯顶点。对上面的例子，顶点 2 的邻居是 1 和 3，二者由边 13 相连；去掉顶点 2 后，顶点 4 的邻居仍是 1 和 3。依次删除 $2,4,1,3$，每次删除的顶点在当时剩余的图中都是单纯顶点。这种顺序叫完全消去序。

一个有限无向图是弦图，当且仅当它存在完全消去序。先验证其中一个方向：假如有完全消去序，任取一个长度至少为四的环，选择环上在该顺序中最早删除的顶点。当它被删除时，其两个环上邻居都还在；单纯性要求这两个邻居相邻。这条连接边不是环边，因而是该环的弦。反方向即每个弦图都存在完全消去序，需要单独证明，不能仅凭一个例子推出。完全消去序可用于一些图算法与稀疏矩阵计算，具体算法仍需考虑如何有效找到该顺序。