A *finite graph* is a pair , where is a finite set (whose elements are called *vertices*) and is a set of unordered pairs from (whose elements are called *edges*). We can visualize a graph in the plane by representing the vertices by dots and connecting to with a curve if . Let be a finite set containing elements. An *-coloring* of a graph is a mapping such that, if , then . In other words, an assignment of a color to each vertex such that two adjacent vertices do not have the same color.

It turns out that we can represent every graph coloring as a solution to a carefully chosen system of polynomial equations. Conversely, given a finite graph , we can construct a system of polynomial equations whose solutions are the colorings of .

Let be a finite graph, and let be a field containing at least elements. Introduce an indeterminate for each vertex of and let be a finite subset containing elements. Introduce an indeterminate , and let . Now suppose is a coloring of , and let for each . Note that . Moreover, if , then , so that , and so . Note that for some coefficients , where , and so divides . In particular, letting , we have . Thus, the coloring corresponds to a solution of the following system of equations.

- for each
- for each

Moreover, every solution to this system yields a coloring. It turns out (by some more advanced results that will be proved later (Hilbert’s Nullstellensatz)) that this system has a solution (and hence has an -coloring) unless the ideal generated by the and is not proper. This is equivalent to the statement that the reduced Gröbner basis of (with respect to any monomial order) is . Thus, when a coloring exists, solving this system will find it.

There are many choices we might make for the field , such as the finite field or any field containing the distinct th roots of unity.

- Consider the graph whose vertices are the integers and whose edges are , , , , , , , , , , , , , and . We can visualize this graph as in the following diagram.
Let and let be our set of colors. Supposing we insist that the vertex 1 is colored by , deduce that has two distinct 3-colorings, which depend on the coloring of vertex 8. Exhibit these two colorings. Show that if is added to , then the graph cannot be 3-colored.

- Consider the graph whose vertices are the integers and whose edges are , , , , , , , , and . (The complete graph on 5 vertices with one edge removed.) We can visualize this graph as in the following diagram.
Let , and let . Show that this graph can be 4-colored, but cannot be 3-colored.

- Let be the graph having 9 vertices and having the edges , , , , , , , , , , , , , , , , , , , , , and . We can visualize this graph as in the following diagram.
Show that this graph has precisely four 4-colorings up to a permutation of the colors. Show that if the edge is added then cannot be 4-colored.

We will use Maple to compute Gröbner bases.

- With our choice of and , evidently we have and . Let be the ideal . Using Maple, we find that this ideal has the Gröbner basis . Now . If , then we have the solution , and if , we have the solution . If we assign the color red to 0, blue to 1, and green to 2, this yields the following two actual colorings of the graph .
Note that these two colorings are really the same up to a permutation of the colors, namely by swapping “blue” and “green”.

Now suppose we add the edge to this graph; we can visualize this as in the following diagram. The added edge is colored in green.

According to Maple, the ideal has reduced Gröbner basis 1 and thus is not a proper ideal. Thus this graph cannot be 3-colored. Another way to convince ourselves that this is true is to note that any 3-coloring of this graph is also a 3-coloring of the original graph . However, in every 3-coloring of , the vertices 3 and 7 have the same color, so that there can be no 3-coloring of with added.

- In this case, , and thus . Let . Using Maple, we see that is a Gröbner basis for this ideal.
From , we may let be any nonzero element of ; say . Now , so that . Let’s say . Now , so that . Let’s say . Then and , so that . This gives a solution , which corresponds to the following explicit coloring of if we let 1 be red, 2 be blue, 3 be green, and 4 be purple.

Now let . Then and . Letting be the ideal generated by the and , using Maple we see that is a Gröbner basis for this ideal; thus does not have a 3-coloring.

- We let , and let . Then and . Suppose also that (without loss of generality) we insist that . Using Maple, we see that the ideal generated by these has as a Gröbner basis the set . We now proceed to find all the solutions of this system.
- Note that from , we have . From , we have .
- Suppose . From , we have .
- Suppose . Then from , we have . From , we have ; if , then yields , and if , then . From , we have . This yields the four solutions , , , and .
- Suppose . Then from , we have . From , we have . If , then yields , and if , then . From we have . This yields the four solutions , , , and .
- Suppose . Then in a similar fashion we get the eight solutions , , , , , , , and .
- Suppose . Then in a similar fashion we get the eight solutions , , , , , , , and .

Now acts on componentwise. (I.e. by permuting the “colors”.) Under this action, we note the following.

- , , , , and . So these six solutions are equivalent up to a permutation of the colors.
- , , , , and . So these six solutions are equivalent up to a permutation of the colors.
- , , , , and . So these six solutions are equivalent up to a permutation of the colors.
- , , , , and . So these six solutions are equivalent up to a permutation of the colors.

Moreover, we can see that , , , and are not equivalent up to a permutation of the colors; thus we have four essentially distinct colorings of . If we let 1 be red, 2 be blue, 3 be green, and 4 be purple, then we can visualize these colorings as follows.

Suppose now that we add the edge . This graph can be visualized as in the following diagram; the added edge is colored green.

If we include with the generators of the ideal as before (and omit ), using Maple we see that this ideal has Gröbner basis ; that is, the graph with added cannot be 4-colored.

Another way to convince ourselves that this graph cannot be colored is to note that any 4-coloring of with added also gives a 4-coloring of . However, in every 4-coloring of , vertices 1 and 5 have the same color.