= Solution
{c}
For even $r\geq2$, take the <complete graph> $K_{r+1}$. It is an $r$-<regular graph> on an odd number of <vertices>. Every <matching in a graph> has at most $r/2$ <edges>, so $r$ colours in a <proper edge colouring> could cover at most $r^2/2$ <edges>. But
$$
|E(K_{r+1})|=\frac{r(r+1)}2>\frac{r^2}2.
$$
Therefore $\chi'(K_{r+1})>r$; <Vizing's theorem> gives \b[$\chi'(K_{r+1})=r+1$]. This includes the <graph triangle> when $r=2$.
For odd $r\geq3$, first construct a <graph> $H_r$ on $r+2$ <vertices>. Start with the <complete graph> on
$$
\{v,a,b,c_1,\ldots,c_{r-1}\},
$$
and delete the <edges> $va$, $vb$, and $c_1c_2,c_3c_4,\ldots,c_{r-2}c_{r-1}$. The pairing is possible because $r-1$ is even. In the initial <complete graph>, every <vertex> has <vertex degree> $r+1$. The distinguished <vertex> $v$ loses two <edges> and every other <vertex> loses exactly one, giving
$$
d_{H_r}(v)=r-1,\qquad d_{H_r}(x)=r\quad(x\ne v).
$$
Take two disjoint copies of $H_r$, with distinguished <vertices> $v,v'$, and add the <edge> $vv'$. The resulting <simple graph> $G_r$ is an $r$-<regular graph>. The added <edge> is the only <edge> between the two copies; each copy has the odd number $r+2$ of <vertices>.
Suppose an $r$-colour <proper edge colouring> existed. At each <vertex>, the $r$ incident <edges> would use all $r$ colours. Thus each colour would form a <perfect matching>. Any <perfect matching> must use $vv'$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by <parity>. Therefore all $r$ colour classes would have to contain the same <edge> $vv'$, a contradiction. Hence <Vizing's theorem> again gives
$$
\boxed{\chi'(G_r)=r+1>r.}
$$
These constructions give <class two regular graphs> for every $r\geq2$. The odd-$r$ construction exhibits the <bridge obstruction to regular edge colouring>; $H_r$ is a <connected graph> because every <vertex> other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those <vertices>.
Back to article page
