Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0. We prove this conjecture in a slightly generalized form. Dedicated to Tibor Gallai on his seventieth birthday