“退化序只限制 N⁺(v) ≤δ。完美消去序还要求N⁺(v)两两相邻，强得多。四圈退化度为2，也有退化序，却没有完美消去序。不能用核分解替代弦图识别。”
形式陈述
弦性是图的性质，消去序是它的一份证书
在有限简单无向图G中，一个圈的弦是连接该圈两个不相邻位置顶点的额外边。G是弦图，当且仅当每个长度至少4的圈都有弦；等价地，G没有长度至少4的诱导圈。三角形不要求再有弦。
顶点v称为单纯顶点，如果它的邻居形成团，即任意两个不同邻居都相邻。度为0或1时条件自动成立。一个顶点排列
定理：有限简单无向图是弦图，当且仅当存在完美消去序。空图以空排列满足约定。定义只使用原图的边，不能在检查过程中暗中补齐缺边，再把补过的图当成原输入。[1, §§2.2–2.3]
直觉
删除时，不制造新邻接
一般消去一个顶点时，剩余邻居可能需要补边才能成为团。完美消去序要求每一步的这些边原本就有。因此“完美”不是指排列唯一，也不是优化一个尚未定义的成本，而是每次删除都不需要修补局部结构。
若图有一个诱导长圈，取这个圈中最早被删除的顶点v。圈上紧邻v的两个点此时都未删除，却没有连边，否则圈不再诱导。因此v的更晚邻居不成团，任何排列都不可能是完美消去序。这证明了定理的一个方向。
极小分隔集为什么必须成团
证明反方向，先取两个不相邻顶点a、b，选一个按包含关系极小的集合S⊆V{a,b}，使删S后a、b处于不同连通分量A、B；若原本已不连通，可取S为空。
每个s∈S都必须在A、B中各有邻居。否则恢复s也无法从a侧穿过它到b侧，S{s}仍能分隔a、b，与极小性矛盾。假设S中有不相邻的x、y，分别在A∪{x,y}和B∪{x,y}中取最短x—y路径。两条路径各有至少两条边，内部顶点分别落在A、B。
每条最短路径内部没有弦，A、B之间没有边，x、y也不相邻。因此把两路拼起来得到诱导长圈，与弦性矛盾。故S必须是团。这里是固定端点a、b的包含极小分隔集，不是要求基数最小，也不是任意分隔集都必须成团。
从两个不相邻单纯顶点完成归纳
对顶点数归纳，证明稍强的命题：非完全弦图至少有两个不相邻的单纯顶点。沿刚才的团分隔集S，考虑更小的诱导图G[A∪S]。若它完全，任取A中一点即单纯；若它不完全，归纳给出两个不相邻单纯顶点。因为S本身是团，这两点不可能都在S，至少一点在A。
A中的点在原图的全部邻居都仍位于A∪S，因此找到的单纯性也对原图成立。对B侧做同样选择，得到另一个单纯顶点，两点不相邻。完全图的任意顶点本来就单纯；诱导子图又保持弦性。于是可以反复删除单纯顶点，直到图空，所记删除次序就是完美消去序。
这个归纳证明存在性，却没有自动给出线性算法：朴素地反复枚举邻居对检查单纯性，可能很慢。实际构造由下一节的搜索完成。
例子与边界
只检查“第一个更晚邻居”是否足够
给定候选排列π及每点位置pos。若N⁺(v)非空，令p(v)为其中位置最小的顶点。只检查
通过全部这些检查，当且仅当π是完美消去序。必要性直接来自更晚邻居成团。充分性自后向前归纳：p(v)的更晚邻居已经成团，而v的其他更晚邻居按位置都晚于p(v)，检查又保证它们邻接p(v)，所以全部落在这个已知的团中；加上p(v)后仍是团。
为避免每次重新扫p(v)的邻接表，把v按p(v)分组。逐个处理p：用数组时间戳标记N(p)，再扫描该组各v的N⁺(v){p}。每份原邻接表只用于一次标记，每份更晚邻居表只用于一次检查，连同建立位置、选p和分组，共O(n+m)时间、O(n+m)存储。不存在“对每个v扫描p(v)整行”这一隐含的二次重复。
若失败，输出三元组(v,p,u)：p、u均晚于v，vp、vu是边而pu不是边。它可立即证明这份排列不合格，但不能单独证明图非弦。
六点图的局部证书
对边01、02、12、23、04、14、45，取π=[5,3,4,2,1,0]：
| v | N⁺(v) | p(v) |
|---|---|---|
| 5 | 4 | |
| 3 | 2 | |
| 4 | 1 | |
| 2 | 1 | |
| 1 | 0 | |
| 0 | 空 | 无 |
只需在含两个更晚邻居的两行核01确为边；其余行至多一个邻居。注意p按π的位置取，不按顶点编号取，所以4和2两行的p都是1。
给四圈补一条边，问题已经改变
四圈01、12、23、30没有完美消去序。加弦02之后，[1,3,0,2]成为合法序列：1、3的更晚邻居都是{0,2}。这证明的是新图的弦性，不是为原四圈找到了更聪明的排列。
任意给出的坏排列也不代表非弦。三点路径0—1—2的排列[1,0,2]失败，[0,2,1]却通过；辨别一张图与核验一份候选证书是不同任务。
推论与应用
从线性识别到同规模的上下界证书
用字典序广度优先搜索生成σ，取π为其反序，再作上述验证。该搜索在任何弦图上都必给出完美消去序，故失败可以判定非弦；通过则由等价定理确定为弦图。在已准备邻接表的RAM口径下，两步合计O(n+m)。
给定合法π，按它的反方向作贪心顶点着色：每次为v取尚未被已着色邻居占用的最小非负颜色。已着色邻居正是N⁺(v)，它们形成团，已有颜色必两两不同，因此v最多需要|N⁺(v)|+1种颜色。
另一方面，每个集合Cᵥ={v}∪N⁺(v)都是团。任意团C的最早顶点v又满足C⊆Cᵥ，因此
保存最大的Cᵥ给出颜色数下界，实际合法着色给出同一个上界。空图约定两值为0。实现以颜色数组时间戳标记邻居颜色，寻找第一个空颜色最多试deg(v)+1个，全部仍O(n+m)，不能每点都清空一个n长标记表。
极大团与最大团都能得到，但输出不同
六点例的最优颜色数为3，一份着色按顶点0,…,5排列为[0,1,2,0,2,0]，{0,1,2}是三点最大团。图的全部极大团还包括{0,1,4}、{2,3}、{4,5}：后二者只有两点，却已不能加入新顶点。
团树要求把这四个极大团全部作为节点；只保留两个最大的三点团会漏掉顶点3、5及其边。若终点只问最优颜色数，一个最大团即可；若要求完整结构，不能用这个较小输出冒充极大团清单。
直接展示非弦的圈，另计提取成本
附件可选地枚举顶点v及它的一对不相邻邻居x、y，在删去v和N(v){x,y}的图中，用BFS找最短x—y路径。若存在，这条最短路径无弦，内部点又都不邻接v，于是加上v得到诱导长圈。每个诱导长圈都能由圈上一点及它两个圈邻居触发一次成功搜索。
这个简单提取器最多尝试O(n³)个三元选择，每次花O(n+m)，保守时间O(n³(n+m))；附件的集合成员检查按Python哈希期望成本计。它用于给小例子输出容易验真的否证，不属于前面的线性识别成本。完整正负记录及输入迁移见终结任务。