Our Very Own Graph Theory Book: MATH 795, Fall 2020

Construct proper colorings of \(G\) by partitioning \(V(G)\) into disjoint sets and assigning a unique color to each disjoint set. A disjoint set is a set of vertices in which no two vertices in the same set are adjacent. Given \(\lambda\) colors, there will be \(\lambda\) ways to choose the color for the first set, \((\lambda - 1)\) ways to choose the color for the second set, \((\lambda - 2)\) ways to choose the color for the third set, and so on. There are then \(\lambda(\lambda -1)(\lambda -2)...\) possible ways to color the vertices of graph \(G\) such that they result in a proper coloring, and it is clear that this is some polynomial.

Let G be a Collection of Vertices (i.e. \(n\) vertices and no edges). Since no vertex is adjacent to any other vertex in the graph, there are \(\lambda\) ways to color each vertex, so \(P(G,\lambda)=\lambda^n\text{.}\)

Let G be a path on \(n\) vertices (\(V=\{x-1, x_2,..., x_n\}, E=\{x_ix_{i+1}\}\)) and begin by coloring \(x_1\text{.}\) There are \(\lambda\) choices of color for \(x_1\text{,}\) and \((\lambda-1)\) choices of color for the \(x_2\) because it is adjacent to the \(x_1\text{.}\) For \(x_3\text{,}\) we also have \((\lambda-1)\) choices of color because it is only adjacent to \(x_2\text{.}\) Similarly, we will have \((\lambda-1)\) choices of color for all of the remaining vertices, meaning \(P(G,\lambda)=\lambda(\lambda-1)^{n-1}\text{.}\)

Consider a proof by induction;

Base Case: Let \(n = 1\text{.}\) The claim clearly holds as we have \(\lambda\) choices of color for the one vertex.

Inductive Step: Assume that the claim holds for a graph on \(n\) vertices. Select any leaf and prune it from the tree. The chromatic polynomial for the resulting tree will be \(\lambda(\lambda-1)^{n-2}\) by assumption. Now, replace the pruned leaf. We can assign any color to this vertex except for that of its neighbour, and thus have \((\lambda-1)\) choices of color. Therefore the chromatic polynomial of Tree is \(P(G,\lambda)=\lambda(\lambda-1)^{n-1}\text{.}\)

Let G be a Complete Graph on \(n\) vertices. We can choose any of the \(\lambda\) colors for the first vertex we color. For the second vertex we color, we have \((\lambda-1)\) choices since it is adjacent to first vertex. Now since each vertex is adjacent to the rest, we have \((\lambda-2)\) choices of color for the third vertex we color, and so on. This yields a polynomial \(\lambda(\lambda-1)(\lambda-2)\text{...,}\) but terminates later when we reach the \(n^{th}\) vertex. If we follow our process for choosing colors, the number of colors we will have available for the last vertex will be \((\lambda-n+1)\text{,}\) because we started at \(\lambda\) and we counted down \((n-1)\) terms. Therefore \(P(G,\lambda)=\lambda(\lambda-1)(\lambda-2)...(\lambda-n+1)=\frac{\lambda!}{(\lambda-n)!}\text{.}\)

Consider a graph \(G\) and one of its edges \(e\text{.}\) Let \(u\) and \(v\) be the two vertices connected to \(e\text{.}\) To be a proper coloring, \(u\) and \(v\) must be colored different colors. In the graph \(G/e\text{,}\) \(u\) and \(v\) are represented by a single vertex, and so, they have the same color. In the graph \(G-e\text{,}\) \(u\) and \(v\) are no longer adjacent, and so they could be colored with the same color or different colors, they are no longer related. This means the number of colorings of \(G-e\) is the same as the total number of colorings of \(G\) and \(G/e\text{.}\) Therefore, \(P(G-e, \lambda)=P(G, \lambda)+P(G/e, \lambda)\) or with some rearranging, \(P(G, \lambda)=P(G-e, \lambda)-P(G/e, \lambda)\text{.}\)

A clique is defined as a subset of vertices such that every pair of vertices in the subset is adjacent. Another way to think of this is that the induced subgraph is complete. Each vertex within the clique is adjacent to \(k-1\) other vertices which are all in turn adjacent to other \(k-1\) vertices in the clique. By the definition of a proper coloring, the colors assigned to each of the vertices in such a clique, including the original vertex must be all distinct. Hence if we have a click of size \(k\text{,}\) there must be \(k\) colors in the proper coloring.

Suppose that \(G\) has \(n\) vertices. We will proceed by induction on the number of edges.

Base case: Let \(G\) have only one edge. Then the \(n-2\) vertices with no edges can be colored with any of our \(\lambda\) colors, and the two vertices on the edge can be colored in \(\lambda(\lambda-1)\) ways, so, \(P(G,\lambda)=\lambda^{n}-\lambda^{n-1}\text{.}\) So, the leading coefficient of \(P(G,\lambda)\) is one.

Inductive Step: We will proceed with strong induction. Assume that the statement is true for all graphs with fewer than \(k\) edges. Assume that \(G\) has \(k\) edges and let \(\beta \in E(G)\) be one of them. By the deletion-contraction property, \(P(G,\lambda)=P(G-\beta, \lambda)-P(G/\beta, \lambda)\text{.}\) Now, since \(G-\beta\) has fewer than \(k\) edges, by the induction hypothesis, \(P(G-\beta, \lambda)\) has a lead coefficent of one and degree \(n\text{.}\) Since \(G/\beta\) has fewer than \(k\) edges and only \(n-1\) vertices, \(P(G/\beta, \lambda)\) also has a lead coefficent of one, but degree \(n-1\text{.}\) Upon subtraction of these polynomials, we see that the lead term is the same lead term as that in \(P(G-\beta), \lambda)\text{,}\) so the lead coeffienct of \(P(G,\lambda\) is one. Therefore, by induction, the statement is true for all graphs with \(n\) vertices and any number of edges.

Again, we will proceed by induction on the number of edges of \(G\text{.}\)

Base Case: As in the proofs of the above theorems, let \(G\) have only one edge. Then the \(n-2\) vertices with no edges can be colored with any of our \(\lambda\) colors, and the two vertices on the edge can be colored in \(\lambda(\lambda-1)\) ways, so, \(P(G,\lambda)=\lambda^{n}-\lambda^{n-1}\text{.}\) So, the coefficient of the second term of \(P(G,\lambda)\) is one, so our statement is true for our base case.

Inductive Step: Again, we will proceed using strong induction. Assume the statement is true for all graphs on \(n\) vertices with fewer than \(k\) edges. Let \(G\) be a graph with \(k\) edges and consider the deletion-contraction property. Since \(G-\beta\) and \(G/\beta\) both have fewer than \(k\) edges, we can apply our induction hypothesis and assume that their chromatic polynomials have the following form: \(P(G-\beta, \lambda)=\lambda^n-a_{n-1}\lambda^{n-1}+a_{n-2}\lambda^{n-2}-...\text{,}\) and \(P(G/\beta, \lambda)=\lambda^{n-1}-b_{n-2}\lambda^{n-2}+b_{n-3}\lambda^{n-3}-...\text{,}\) where \(a_{n-1}\) is the number of edges in \(G-\beta\) and \(b_{n-2}\) is the number of edges in \(G/\beta\text{.}\) Now since \(P(G,\lambda)=P(G-\beta, \lambda)-P(G/\beta, \lambda)\text{,}\) by the deletion contraction property;

\(P(G,\lambda)=(\lambda^n-a_{n-1}\lambda^{n-1}+a_{n-2}\lambda^{n-2}-...)-(\lambda^{n-1}-b_{n-2}\lambda^{n-2}+b_{n-3}\lambda^{n-3}-...)\)

\(P(G,\lambda)=\lambda^n-(a_{n-1}+1)\lambda^{n-1}+(a_{n-2}+b_{n-2})\lambda^{n-2}-...\)

Now since \(G-\beta\) is obtained from \(G\) by the removal of one edge, \(a_{n-1} = (k - 1)\text{,}\) so \(a_{n-1}+1 = k\text{,}\) and the statement is true. Therefore by induction, the statement is true for all graphs with \(n\) vertices and any number of edges.

We know that \(P(G,0)\) is the number of ways to color the graph \(G\) with no colors. But a graph cannot be colored with no colors, so \(a_0=0\text{.}\)

(By Strong Induction) We want to show that the statement is true for all graphs, so we will use induction on the number of edges in the graph to do so.

Base Case: If our graph has a single edge, then the chromatic polynomial of the graph with \(n\) and one edge is \(x^n-x^{n-1}\text{.}\) This has alternating signs, so our base case holds.

Now suppose this statement holds for all graphs with fewer than \(k\) edges. Now we want to show that the statement holds true for a graph with \(k\) edges.

We know from the deletion-contraction theorem that \(P(G_k,\lambda)=P(G_k-e,\lambda)-P(G_k/e,\lambda)\text{.}\) Now since both \(P(G_k-e,\lambda)\) and \(P(G_k/e,\lambda)\) both have \(k-1\) edges, our induction hypothesis holds for both of these graphs, so they take the form

\(P(G_k-e,\lambda)=\lambda^n-a_{n-1}\lambda^{n-1}+a_{n-2}\lambda^{n-2}-\cdots\)

\(P(G_k/e,\lambda)=\lambda^{n-1}-b_{n-2}\lambda^{n-2}+b_{n-3}\lambda^{n-3}-\cdots\)

So by our deletion contraction theorem we have that

\(P(G_k,\lambda)=(\lambda^n-a_{n-1}\lambda^{n-1}+a_{n-2}\lambda^{n-2}-\cdots)-(\lambda^{n-1}-b_{n-2}\lambda^{n-2}+b_{n-3}\lambda^{n-3}-\cdots)\)

\(\lambda^n-(a_{n-1}+1)\lambda^{n-1}+(a_{n-2}+b_{n-2})\lambda^{n-2}-\cdots\)

Thus, the signs alternate for a graph with \(k\) edges, so our statement is true for all graphs.

We want to show that \(|a_{m+1}|\lt |a_m|\) for all \(m\gt \frac{n}{2}\)

Case 1: Let \(G\) be a tree \(T_n\) From previous proofs we know that for a graph of a tree \(P(T_n,\lambda)=\lambda(\lambda-1)^{n-1}\) so we have that \(a_{m}=(-1)^{n-m}\binom{n-1}{m-1}\) and thus we need to show that \(\binom{n-1}{m}\lt \binom{n-1}{m-1}\)

So we need to show that \(\frac{(n-1)!}{m!(n-m-1)!}\lt \frac{(n-1)!}{(m-1)!(n-m)!}\) then since by our statements regarding \(n\) and \(m\) we know that \(n-m\lt m\) so we have

\(n-m\lt m\) which tells us that

\(m!(n-m-1)!\gt (m-1)!(n+1)!\) so we have

\(\frac{(n-1)!}{m!(n-m-1)!}\lt \frac{(n-1)!}{(m-1)!(n-m)!}\)

Thus the inequality holds

Case 2: If \(G\) is not a tree, then we can use an iterative application of the deletion-contraction theorem along with the following theorem 4.3.19 to prove the inequality.

If \(G\) is not a tree then remove edge \(e\) where \(e\) is an edge that is part of a cycle. Then by the deletion contraction theorem and theorem 4.3.19 that we subtract the polynomials, and since the signs of the corresponding coefficients alternate we know the corresponding coefficients will add their absolute values. So the contracted graph will have

\(0=|a'_n|\lt 1=|a'_{n-1}|\lt |a'_{n-2}|\lt \cdots \left|a'_{\frac{n-1}{2}+1}\right|\)

So since their absolute values add up, and since \(G-e\) and \(G/e\) both satisfy the inequalities, the inequality also holds for the graph \(G\text{.}\)

Because we know from theorem 4.3.19 that the coefficients of a chromatic polynomial alternate in sign, we know our chromatic polynomial takes the form

\(P(G,\lambda)=\sum \limits_{m=1}^{n} a_m\lambda^m\)

where \(a_m\ge 0\) if \(n\equiv m \mod 2\) (since the polynomial alternates in sign). Then if we multiply \((-1)^nP(G,\lambda)\text{,}\) this quantity will be greater than or equal to zero if \(\lambda\lt 0\text{.}\) So it remains to show that it cannot be equal to zero. Since we know that \(a_n=1>0\text{,}\) we know that \((-1)^nP(G,\lambda)\gt 0\text{.}\) So this product is strictly greater than zero, Thus, no negative value of \(q\) can be a root of the chromatic polynomial.