Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 17H (Graph Theory)

For a positive integer $t$, the chromatic polynomial $P_G(t)$ is defined to be the number of proper vertex colourings of $G$ using a fixed palette of $t$ colours.

We prove that this counting function is a polynomial by induction on the number of edges. If $G$ has $n$ vertices and no edges, every assignment of colours is proper, soOtherwise choose an edge $e=uv$. Every proper colouring of $G-e$ either gives $u,v$ different colours, in which case it is a colouring of $G$, or gives them the same colour, in which case it corresponds to a proper colouring of the contracted graph $G/e$. Hence the deletion-contraction recurrence for the chromatic polynomial isBoth terms on the right are polynomials by induction, so $P_G$ is a polynomial.

Factor the proposed polynomial:In particular,By the two-colourability criterion for bipartite graphs, every finite bipartite graph has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.

It is nevertheless a chromatic polynomial. Start with the complete graph $K_3$, whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The chromatic polynomial after attaching a leaf therefore gives

Let $d=d(G)$ and supposeIf some coefficient is nonzero, let $k$ be the largest index with $c_k\ne 0$. Choose a pathwhose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus

By the walk count from powers of an adjacency matrix,Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ givesa contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter:

Take the infinite familyEach complete graph is connected and has graph diameter one. If $A_n$ is its adjacency matrix, thenand direct multiplication gives the adjacency-matrix quadratic relation for a complete graphConsequentlyso $I,A_n,A_n^2$, which are precisely the powers through $d(G_n)+1=2$, are linearly dependent for every $n\ge 2$.