Ladder Graph and Graph Theory

Question

I am trying to prove that(By induction and Deletion Contraction Theorem) the following chromatic polynomial holds for all values of n on a ladder graph: $$(−1)(^2−3+3)^{−1}$$ I have seen some explanations of this in other areas on this site, but none utilize (or properly explain) the use of induction. Additionally, some neglect to explain why it is necessary that $$(^2−3+3)^{−1}$$ needs to be raised to the power of n-1.

Answer 1

The use of induction

Assume that the chromatic polynomial of $L_n$ is $(−1)(^2−3+3)^{−1}$. Consider how to extend any $k$-colouring of $L_n$ to the extra two points of $L_{n+1}$.

For definiteness, let the new rung be $a-b$ which is joined to rung $y-z$. Let $a$ be joined to $y$ and $b$ joined to $z$.

Case 1 If $a$ is coloured the same as $z$.

Then there are $k-1$ choices for $b$.

Case 2 If $a$ is not coloured the same as $z$.

Then there are $k-2$ choices for $a$ and a further $k-2$ choices for $b$.

The total number of $k$-colourings is now

$(−1)(^2−3+3)^{−1}$ multiplied by $(k-1)+(k-2)^2=^2−3+3$.

I hope this makes the induction and the $^2−3+3$ term easier to understand.