Coloring Vertices and Measuring a Graph
A vertex coloring assigns labels, called colors, to vertices so that adjacent vertices receive different labels. The least number of colors that permits such an assignment is an important graph parameter: it records how much separation the edges require. Degree parameters describe a different aspect of the graph. They count local incidences at vertices, while order counts the vertices themselves and average degree summarizes the degrees across the whole graph. Keeping these quantities distinct is essential: they are related, but none of them is a substitute for the others.
Throughout, graphs are finite and simple. Thus there are no loops or multiple edges. Write \(G=(V,E)\), with order \(n=|V|\) and size \(m=|E|\). An independent set is a set of vertices no two of which are adjacent.
Some of the \(k\) color classes in a coloring may be empty. In a coloring using the minimum possible number of colors on a nonempty graph, none is empty: if a class were empty, that color could be removed. Each nonempty color class is an independent set, because any edge within the class would have endpoints assigned the same color. Conversely, a partition of \(V\) into independent sets gives a proper coloring by assigning a different color to each part.
For an edge \(uv\), the vertices \(u\) and \(v\) are neighbors. The degree \(\deg(v)\) is the number of neighbors of \(v\). For a nonempty graph, the minimum degree \(\delta(G)\) is the least vertex degree, and the maximum degree \(\Delta(G)\) is the greatest. Its average degree is the arithmetic mean of all vertex degrees, denoted here by \(\overline d(G)\). The empty graph has no vertex degrees, so \(\delta(G)\), \(\Delta(G)\), and \(\overline d(G)\) are left undefined for it.
Order \(n\) counts vertices, not edges; size \(m\) counts edges. The three degree quantities each describe degrees differently: \(\delta(G)\) and \(\Delta(G)\) are the extremes, while \(\overline d(G)\) is their overall mean. An isolated vertex has degree \(0\), so it can make the minimum degree zero without changing the number of edges.
Degree Sums and Average Degree
Proof. Count incidences \((v,e)\) in which vertex \(v\) is an endpoint of edge \(e\). Counting first by vertices gives \(\sum_{v\in V}\deg(v)\), since each vertex contributes one incidence for each incident edge. Counting by edges gives \(2|E|\), since every edge in a simple graph has exactly two distinct endpoints. Therefore \(\sum_{v\in V}\deg(v)=2|E|\), including when \(V\) and \(E\) are both empty. If \(n>0\), every degree lies between \(\delta(G)\) and \(\Delta(G)\). Adding these \(n\) inequalities and dividing by the positive number \(n\) gives \(\delta(G)\le \frac{1}{n}\sum_{v\in V}\deg(v)\le\Delta(G)\). The middle expression is \(\overline d(G)\). \(\square\)
This identity is also a useful consistency check: a proposed degree list for a graph must sum to an even number, twice the edge count. The inequalities say the average cannot fall below every degree or exceed every degree. They do not say that the average must equal either extreme.
Worked Example: A Path and Its Degree Parameters
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). This is a path with four vertices. Its order is \(n=|V|=4\), and its size is \(m=|E|=3\).
Vertex \(1\) is incident only with edge \(12\), so \(\deg(1)=1\). Vertex \(2\) is incident with \(12\) and \(23\), so \(\deg(2)=2\). Vertex \(3\) is incident with \(23\) and \(34\), so \(\deg(3)=2\). Vertex \(4\) is incident only with \(34\), so \(\deg(4)=1\). Hence \(\delta(G)=1\) and \(\Delta(G)=2\), while \(\overline d(G)=(1+2+2+1)/4=6/4=3/2\).
The alternating assignment \(c(1)=1,\ c(2)=2,\ c(3)=1,\ c(4)=2\) is proper, since each of the three listed edges has differently colored endpoints. At least two colors are needed because \(12\in E\) and the endpoints of an edge cannot have the same color. Therefore \(\chi(G)=2\).
Check: The degrees sum to \(1+2+2+1=6\), and twice the listed edge count is \(2\cdot3=6\). The average \(3/2\) lies between the minimum degree \(1\) and maximum degree \(2\).
A Basic Bound from Maximum Degree
The maximum degree gives a simple guarantee for constructing a coloring. It is a guarantee, not usually an exact formula: the coloring produced may use more colors than necessary.
Proof. List the vertices in any order, and color them one at a time using colors from the set \(\{1,\ldots,\Delta(G)+1\}\). Suppose the first \(j-1\) vertices have been colored properly, and consider the \(j\)th vertex \(v\). At most \(\deg(v)\le\Delta(G)\) colors appear on its already-colored neighbors, because \(v\) has at most \(\Delta(G)\) neighbors in total. Thus at most \(\Delta(G)\) of the \(\Delta(G)+1\) available colors are forbidden by these neighbors. At least one color remains; assign it to \(v\). This preserves properness among all vertices colored so far. Repeating the step colors every vertex, and any edge has differently colored endpoints because when its later endpoint was colored, the earlier endpoint’s color was forbidden. Hence a proper coloring with at most \(\Delta(G)+1\) colors exists, so \(\chi(G)\le\Delta(G)+1\). \(\square\)
Worked Example: Greedy Coloring a Star
Let \(G=(V,E)\), where \(V=\{0,1,2,3,4\}\) and \(E=\{01,02,03,04\}\). The center \(0\) has degree \(4\), and each of the four other vertices has degree \(1\). Thus \(n=5\), \(m=4\), \(\delta(G)=1\), \(\Delta(G)=4\), and \(\overline d(G)=(4+1+1+1+1)/5=8/5\).
Color in the order \(0,1,2,3,4\). Give vertex \(0\) color 1. Each subsequent vertex is adjacent only to \(0\), so color 1 is forbidden and color 2 is available; assign color 2 to vertices \(1,2,3,4\). The resulting color classes are \(\{0\}\) and \(\{1,2,3,4\}\). The coloring is proper because every edge has one endpoint \(0\) and one endpoint among \(1,2,3,4\).
One color cannot work because the graph contains the edge \(01\), so \(\chi(G)\ge2\). The displayed coloring uses two colors, giving \(\chi(G)=2\). The maximum-degree theorem gives only \(\chi(G)\le4+1=5\), which is valid but not sharp here.
Check: The degree sum is \(4+1+1+1+1=8\), equal to \(2m=2\cdot4=8\). The average degree is \(8/5\), between \(1\) and \(4\).
Degree Parameters Do Not Determine the Chromatic Number
The same degree information can occur in graphs with different chromatic numbers. A cycle is a useful way to see this: its vertices all have degree \(2\), but the parity of its length affects whether two colors suffice. The next example calculates the parameters and colorings explicitly.
Worked Example: Two Regular Graphs, Different Chromatic Numbers
First let \(G_5=(V_5,E_5)\), where \(V_5=\{1,2,3,4,5\}\) and \(E_5=\{12,23,34,45,51\}\). Each vertex has degree \(2\): the neighbors are \(2,5\) for vertex \(1\), \(1,3\) for vertex \(2\), \(2,4\) for vertex \(3\), \(3,5\) for vertex \(4\), and \(4,1\) for vertex \(5\). Thus \(\delta(G_5)=\Delta(G_5)=\overline d(G_5)=2\), with \(n=5\) and \(m=5\).
Two colors cannot properly color \(G_5\). If vertex \(1\) has color 1, then the edges \(12,23,34,45\) force the successive colors \(2,1,2,1\) on vertices \(2,3,4,5\). But edge \(51\) then joins two vertices of color 1. Three colors do suffice: assign colors \(1,2,1,2,3\) to vertices \(1,2,3,4,5\), respectively. Checking the listed edges, the endpoint colors are \(1\) and \(2\) on \(12\), \(2\) and \(1\) on \(23\), \(1\) and \(2\) on \(34\), \(2\) and \(3\) on \(45\), and \(3\) and \(1\) on \(51\). Therefore \(\chi(G_5)=3\).
Now let \(G_6=(V_6,E_6)\), where \(V_6=\{1,2,3,4,5,6\}\) and \(E_6=\{12,23,34,45,56,61\}\). Each vertex has degree \(2\), so \(\delta(G_6)=\Delta(G_6)=\overline d(G_6)=2\); here \(n=6\) and \(m=6\). Assign colors \(1,2,1,2,1,2\) in vertex order. The edges \(12,23,34,45,56,61\) have endpoint colors \(1,2\), \(2,1\), \(1,2\), \(2,1\), \(1,2\), and \(2,1\), respectively. Thus this is a proper two-coloring. Since the graph has an edge, it cannot use just one color, so \(\chi(G_6)=2\).
Check: For \(G_5\), the degree sum is \(5\cdot2=10=2\cdot5=2m\). For \(G_6\), it is \(6\cdot2=12=2\cdot6=2m\). Both graphs have minimum, maximum, and average degree \(2\), yet their chromatic numbers differ.
Common Pitfall: Confusing a Total with an Average
For the four-vertex path above, the degree sum is \(1+2+2+1=6\). A common error is to call \(6\) the average degree. It is the total degree, which equals twice the number of edges. The average divides that total by the number of vertices: \(6/4=3/2\). Another error is to treat the minimum degree as the degree of a particular chosen vertex; \(\delta(G)\) is the least degree across all vertices, whereas \(\deg(v)\) refers to one specified vertex.
Color classes and degree parameters answer different questions. A color class records which vertices can share a color without an edge between them. The order and degree parameters count vertices and incidences. The maximum-degree coloring bound connects these subjects, but it can be loose, as the star example demonstrates. In particular, knowing that every vertex has degree \(2\) does not by itself determine the chromatic number, as the two cycle examples show.
Check Your Understanding
For each question, state any graph’s vertex set and edge set explicitly when you use an example.
- Give a proper coloring of the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), and justify its chromatic number.
- A graph has \(n=6\) vertices and degrees \(1,1,2,2,2,2\). Compute its average degree and the number of edges, assuming these are the degrees of a finite simple graph.
- Explain why every nonempty graph containing an edge has chromatic number at least \(2\).
- Apply the maximum-degree coloring argument to a graph with \(\Delta(G)=3\). How many colors does the bound guarantee are sufficient?
- Can two graphs with the same minimum, maximum, and average degree have different chromatic numbers? Use the worked cycle example to justify your answer.