A proper vertex colouring of a graph $G$ is a function $\kappa$ defined on
the vertices of $G$ such that if $v$ and $w$ are any two neighbouring
vertices, then $\kappa(v)$ does not equal $\kappa(w)$. A simple result in
graph theory is the following: let G be a finite graph such that each
vertex has degree at most $d$. Then there is a proper colouring of $G$
that uses at most $d+1$ colours. (This means that the function $\kappa$
takes at most d+1 distinct values.)To prove this, we choose some ordering of the vertices:
$v_1,v_2,\dots,v_n$ and colour them inductively as follows. Having
coloured $v_1,\dots,v_{k-1}$, we would like to colour $v_k$. By
hypothesis, $v_k$ has at most d neighbours, so there are at most d
neighbours of $v_k$ amongst the vertices $v_1,\dots,v_{k-1}$. Therefore,
there are at most $d$ colours that we must avoid when choosing a colour
for $v_k$. Since there are $d+1$ colours available to us, we can
arbitrarily choose some colour that is not one of the ones we have to
avoid. And thus the induction continues.
So this proof is saying that no two adjacent vertcies numbered from one to $k-1$ is of the same color?
$v_k$ has at most d neighbors means that $v_k$ is at most connected to $d$ vertices?
If $d=5$, then we must avoid 5 colors. We have $d+1=6$ colors available that we can choose. Shouldn't $d+1$ include the 5 we must avoid, so the number of colors available to color with is actually one or not $d+1$? But this is a contradiction. In fact, I think we don't know how many colors on the color palette we can choose.
Could we prove this by well-ordering principle?
I think I'd prove this via contradiction instead.
This proof doesn't mention the function $\kappa(v)$ once. Why is $\kappa(v)$ mentioned?
Best Answer
Well yes, but more usefully it's saying that between those vertices which are adjacent to $v_k$, there are at most $d$ colours.
I think you're getting confused between the number of colours in our palette, and the number of colours we can validly assign to $v_k$. There are $d+1$ colours in our palette, but at most $d$ of those would result in an invalid colouring if applied to $v_k$.
Therefore, we always have at least one choice of colour for $v_k$ which will result in a valid colouring.
I don't see how the well-ordering principle is necessary or useful here.