Colouring graph's edges.

Question

Let $G$ be a graph in which each vertex except one has degree $d$. Show that if $G$ can be edge-coloured in $d$ colours then

(1) $G$ has an odd number of vertices,

(2) $G$ has a vertex of degree zero

Please help me with it.

Answer 1

Hint:

• Let $u$ be the vertex of non-$d$ degree. We have that $\deg(u) < d$, so there is a color $c$ not used by that vertex.
• Remove all the edges of color $c$, either
  • $\deg(u)$ is still smaller and we reduced the problem, or
  • all the degrees are equal, but the sum of degrees we removed is an even number.

I hope this helps $\ddot\smile$