# Tutte 1-factor theorem to prove total chromatic number of complete multipartite graphs

Consider a complete multipartite graph on $$n$$ vertices having maximum degree $$\Delta$$. Then, it is known that the total chromatic number of the graph is $$\le\Delta+2$$. The proof uses the fact that a maximum independent set has size more than or equal to $$n-\Delta-1$$.

But, in the classic text by H P Yap,"Total Colourings of Graphs", it is also remarked that the above result follows directly from Tutte's 1-factor theorem. I am unable to prove the same. For, suppose if the graph were having an odd number of vertices, then how could Tutte's theorem help there? If the 1-factor theorem were applied to a subgraph of the graph with an independent set removed, then how would we ensure distinct perfect matchings? Any hints? Thanks beforehand.