= Solution
{c}
First reduce the <unicyclic graph> to its unique <graph cycle> $C$. Delete the <edges> of $C$ but retain every <vertex>. The remaining <graph> is a <forest>, since any surviving <graph cycle> would be a second one in $G$. Each of its <connected components of a graph> contains a <vertex> of $C$: follow a <graph path> to $C$ in the original <connected graph>, stopping at the first <vertex> of $C$; this initial segment uses no <edge> of $C$.
No such <connected component of a graph> contains two <vertices> of $C$. Otherwise, on the <tree> <graph path> between them, choose two successive visits to $C$. The segment between these visits has no internal <vertex> on $C$ and uses no <edge> of $C$. Combining it with either connecting arc of $C$ gives a second <graph cycle>, a contradiction. Thus the remaining <graph> consists of <trees>, each rooted at exactly one <vertex> of $C$.
After choosing a <proper vertex colouring> of $C$ from $q$ colours, colour these <rooted trees> away from their roots. Each of the $n-\ell$ off-<graph cycle> <vertices> has one already coloured <parent in a rooted tree>, leaving exactly $q-1$ choices. The <multiplication principle> therefore gives
$$
p_G(x)=(x-1)^{n-\ell}p_{C_\ell}(x).
$$
Equivalently, this repeatedly applies the <chromatic polynomial after attaching a leaf> formula.
To compute the <chromatic polynomial of a cycle>, the base case is the <graph triangle>:
$$
p_{C_3}(x)=x(x-1)(x-2)=(x-1)^3-(x-1).
$$
For $s\geq4$, deleting a <cycle graph> <edge> gives a <path graph> on $s$ <vertices>, while <edge contraction> gives $C_{s-1}$. The <chromatic polynomial> of that <path graph> is $x(x-1)^{s-1}$, by choosing the colour of its first <vertex> and then each successive <vertex>. Hence the <deletion-contraction recurrence for the chromatic polynomial> gives
$$
p_{C_s}(x)=x(x-1)^{s-1}-p_{C_{s-1}}(x).
$$
Using <mathematical induction>, substitute $p_{C_{s-1}}(x)=(x-1)^{s-1}+(-1)^{s-1}(x-1)$ to obtain
$$
p_{C_s}(x)=(x-1)^s+(-1)^s(x-1).
$$
Multiplying by the factor for the attached <trees> proves the <chromatic polynomial of a unicyclic graph> formula
$$
\boxed{p_G(x)=(x-1)^n+(-1)^\ell(x-1)^{n-\ell+1}.}
$$
Back to article page
