“Brooks 定理为图染色提供结构性保证：完全图和奇圈解释了贪心上界的全部连通极端情形。它并不提供一般图色数的精确求解方法，也不能凭 $\chi\le\Delta$ 判定是否还能少用一色。”
“设 $G$ 是有限、简单、连通的图，$\Delta=\max {v\in V(G)}\deg(v)$ 为最大度，$\chi(G)$ 为正常顶点着色的色数。Brooks 定理断言：若 $G$…”
形式陈述
长度
进一步限制重复方式，可得到不同对象：迹（trail）不重复边；路（path，本条指简单路径）不重复顶点；圈（cycle，本条指简单圈）是长度
一条长度为
同一圈可以从不同起点、沿两个方向写成多个顶点序列。讨论图中“有几个圈”时，通常把这些写法识别为同一个圈；讨论带起点的行走或矩阵幂计数时，则必须保留指定的起终点和长度。
用边身份记录多重图中的行走
若允许自环和平行边，取有限顶点集
其中
在这个模型中，圈是正长度的闭迹，且
下文未另作说明的例子与论证仍使用开头的有限简单图约定。
直觉
这组概念区分的是沿途消耗什么。行走只要求下一步有边可走；迹要求每条边至多使用一次；路要求不再回访已经到过的顶点。圈保留一次必要的回访——回到出发点——而禁止途中绕回旧顶点。
“能从一处到另一处”与“怎样走到那里”也有区别。可达性只需要存在一种连接；一旦某段行走中出现回绕，通常可以删去这段多余经历，保留起点和终点。因此许多存在性问题可先允许行走，再化简成路。
例子与边界
一个图区分四种概念
让两个三角形
特别地，
附带模2标记时，奇支撑闭走提取可保证找到圈：每次截出内部无重复顶点的闭段，若标记边经过偶数次便删除，若为奇便返回。整体为奇保证最终会遇到奇段；同边往返的贡献为偶，不会被误报为两边圈。非负权还保证返回圈不比输入闭走更贵。
为什么行走可以删成路
若
这证明“存在行走”与“存在路”给出同样的可达性。但它没有证明每个非平凡闭行走都含圈：
边权改变最短问题
若所有边权非负，删去闭子段不会增加总权重。固定两个可达的不同顶点，有限图中连接它们的简单路径只有有限多条，因而其中存在权重最小者。任意行走又能化简为一条不更贵的简单路径，所以这个最小值也就是所有行走的最小权重；这里同时说明了最优解为何存在、为何可选为简单路径。
若无向图有一条负权边，允许重复边的行走可在其两端来回走，每次往返都减少两倍该边权重的绝对值。对同一连通分量中的任意起终点，可以先走到这条边、重复往返，再走到终点，因而行走权重没有下界。其他连通分量不受它影响；若只允许简单路径，可达端点之间仍只有有限个候选，最小值仍存在。最短路算法的权重条件必须结合允许的行走方式与查询端点解释。
推论与应用
两条不同的简单路径会暴露一个圈。 对不同顶点
一条边是桥，当且仅当它不属于任何圈。若边在圈上，删除后仍可沿圈的另一侧连接端点，因此不会断开原连通分量。反过来，若删边后两端仍连通，取一条不使用该边的连接路，与该边合成圈。这个判据把“删除后全局断开”转化为“原图里存在绕行”。
搜索算法常维护一个已经发现的前驱关系，从而给可达性提供具体路径证据。无权图的广度优先搜索按经过边数逐层探索，首次发现顶点时得到最短长度；深度优先搜索则帮助识别回边、圈和割结构。两者都不需要枚举所有行走。
Euler 迹要求覆盖每条边一次，Hamilton 路与圈要求覆盖每个顶点一次。前面的“8”字图可沿闭迹使用所有边，却无法用一个简单圈覆盖两个三角形的全部顶点。这不是术语差别，而是重复限制不同造成的结构障碍。
参考资料
-
Robert Sedgewick、Kevin Wayne，Algorithms，第 4 版，2011，配套在线教材§4.1 Undirected Graphs，Glossary 与路径搜索。该书把不重复边的对象称为 path，本页称为迹；使用定义而非译名对照。
-
Oscar Levin，Discrete Mathematics: An Open Introduction，Chapter 4：路径、圈、树和遍历。
-
Reinhard Diestel，Graph Theory，5th ed.，2017，§1.3、§1.5：路、圈与树；不同教材的 path、walk 中文译名应与各自定义核对。
-
Jeff Erickson，Algorithms，Chapter 5：基本图算法与图搜索。