Brooks' Theorem says a connected graph that is not a complete graph or an odd cycle has chromatic number at most its maximum degree. In combinatorics, it gives a strong upper bound for vertex coloring.
Brooks' Theorem is a graph coloring result in combinatorics that gives a fast upper bound for the chromatic number of a connected graph. If a graph is connected and is not a complete graph and not an odd cycle, then you can color its vertices with at most Δ colors, where Δ is the graph’s maximum degree.
That statement matters because the chromatic number is usually hard to find exactly. Brooks’ Theorem does not always tell you the exact answer, but it tells you you do not need more than the maximum degree in the usual case. So if a graph has maximum degree 5, the theorem says 5 colors are enough unless the graph is one of the special exceptions.
The two exceptions are the reason the theorem is remembered so clearly. A complete graph with n vertices needs n colors, since every vertex touches every other vertex. An odd cycle needs 3 colors even though its maximum degree is 2, so it breaks the simple “use Δ colors” pattern. Those exceptions show that graph structure matters, not just degree count.
A useful way to read the theorem is as a comparison between local and global behavior. The maximum degree is a local measurement, it only looks at the busiest vertex. The chromatic number is global, because it depends on how the whole graph fits together. Brooks’ Theorem says that for most connected graphs, the global coloring problem is controlled by that local degree bound.
There is also a common special case in Combinatorics: trees. A tree is connected, has no cycles, and is never complete unless it is just a single vertex or an edge. Since trees are bipartite, they can be colored with 2 colors, which fits the theorem’s general message that sparse graphs are easier to color. If you see a problem with a tree or a graph that looks tree-like, Brooks’ Theorem is usually more than enough to justify a low color count.
In practice, the theorem is often used as a shortcut. Instead of trying to build the perfect coloring from scratch, you check the graph’s maximum degree, rule out the exception cases, and then use the theorem to give a clean upper bound on the chromatic number.
Brooks’ Theorem is one of the main tools for turning a hard coloring problem into a manageable one. In graph theory, chromatic numbers can be tricky to compute exactly, so a theorem that gives a sharp bound is extremely useful on problem sets and proofs.
It also teaches you how graph structure changes coloring behavior. A complete graph forces every vertex to use a different color, while an odd cycle needs one more color than its degree might suggest. That contrast is a big theme in combinatorics: local properties like degree are helpful, but they do not always tell the whole story.
The theorem shows up whenever you need to justify that a graph is colorable with at most Δ colors. That kind of statement comes up in proofs, homework problems, and longer graph theory arguments where you compare the graph to known classes like trees, cycles, and complete graphs.
Brooks’ Theorem also connects to algorithmic thinking. When you study coloring algorithms, a theorem like this tells you what kind of bound to aim for before you start searching for an actual coloring. If the graph is not one of the exceptional cases, you already know the answer cannot exceed the maximum degree.
Keep studying COMBINATORICS Unit 12
Visual cheatsheet
view galleryChromatic Number
Brooks’ Theorem is a bound on the chromatic number, so you need the chromatic number first to use it correctly. The theorem does not give an exact value for every graph, but it narrows the possible answers. In many problems, you use Brooks’ Theorem to show the chromatic number is at most Δ, then check whether the graph has a special structure that forces a smaller or larger exact value.
Vertex Coloring
Vertex coloring is the process Brooks’ Theorem is about. The theorem tells you how many colors you may need to color vertices so adjacent vertices never match. When you are given a graph and asked for a proper coloring, Brooks’ Theorem gives a clean upper bound before you try to construct the coloring by hand.
Graph Degree
The maximum degree, written Δ, is the number that Brooks’ Theorem uses as its bound. This makes degree a quick first check in coloring problems. If a graph has a high-degree vertex, you know the theorem may still keep the chromatic number under control, as long as the graph is not complete or an odd cycle.
greedy coloring algorithm
A greedy coloring algorithm colors vertices one at a time and uses the first available color. Brooks’ Theorem gives theoretical support for why a graph can often be colored efficiently with a small number of colors. The theorem and the greedy method are not the same thing, but they often appear together when you want to explain or construct a valid coloring.
A graph theory problem may give you a connected graph and ask for an upper bound on its chromatic number. Your first move is to check the maximum degree, then see whether the graph is complete or an odd cycle. If it is neither, Brooks’ Theorem lets you state that the graph is colorable with at most Δ colors.
You may also use it in a proof where the goal is not the exact chromatic number, but a clean justification that a coloring exists with no more than a certain number of colors. On short-answer or proof-style questions, naming the theorem and checking the exception cases is usually enough. If the graph is a tree, you can often combine Brooks’ Theorem with the fact that trees are bipartite to justify a 2-coloring instead of building a complicated argument from scratch.
Brooks’ Theorem is not the chromatic number itself. The chromatic number is the minimum number of colors needed, while Brooks’ Theorem gives an upper bound for many connected graphs. A lot of confusion comes from the fact that the theorem often gets you close to the exact value, but it does not always determine it.
Brooks’ Theorem says a connected graph that is not complete and not an odd cycle has chromatic number at most its maximum degree.
The theorem is a shortcut for vertex coloring problems because it replaces an exact search with a usable upper bound.
Complete graphs and odd cycles are the two standard exceptions, so you should check them first.
The maximum degree is a local measurement, but the chromatic number is global, and Brooks’ Theorem connects the two.
Trees fit the theorem’s general pattern of sparse graphs needing few colors, and they are 2-colorable because they are bipartite.
Brooks’ Theorem says that for a connected graph that is not complete or an odd cycle, the chromatic number is at most the graph’s maximum degree. In combinatorics, it is a standard result in vertex coloring. It gives a strong upper bound without requiring you to find the exact coloring every time.
Complete graphs need a different color on every vertex, so the chromatic number is exactly the number of vertices, not just the maximum degree. Odd cycles also break the usual pattern because they need 3 colors even though every vertex has degree 2. Those two cases show that degree alone does not always control coloring.
Find the graph’s maximum degree, then check whether the graph is complete or an odd cycle. If it is neither, you can state that the graph can be colored with at most that many colors. That is often enough to finish a proof or justify an upper bound in a homework problem.
Not always. It usually gives an upper bound, not the exact minimum. In some graphs the bound is tight, but in others the real chromatic number is smaller, like trees, which are 2-colorable even though their maximum degree may be larger.