What do they mean when they say "a blue $3$-regular subgraph"?

Question

In page 4 of the following http://web.mat.bham.ac.uk/D.Kuehn/RamseyGreg.pdf the text says

In any graph the number of vertices with odd degree must be even. For this reason there cannot exist a red 5-regular subgraph of $K_9$ or a blue 3-regular subgraph of $K_9$. This implies that in a complete 2-coloured graph of order nine there must be at least one vertex which is incident to at least six red or at least four blue edges.

I don't understand why "there cannot exist..." and why in turn "This implies that...". For example, if I take inside $K_9$ a $K_4$ and paint it all blue, don't I get a blue $3$-regular subgraph? It might be that I don't understand what the author means by "blue $3$-regular subgraph". Could someone clarify?

Answer 1

He means you cannot find a subset of edges that includes all $9$ vertices of $K_9$ that is $3$ or $5$ regular. You certainly can find a $5$-regular subgraph of $K_9$-just take $K_6$. What he really wants to do is justify the next sentence-that in any two coloring of $K_9$ there is a vertex with either six or more red edges or a vertex with four or more blue edges. As each vertex of $K_9$ has degree $8$, the only way this could fail would be if you could partition $K_9$ into a $5$-regular red piece and a $3$-regular blue piece. The parity argument is enough to show this is not possible.

Answer 2

If you take a $K_9$ and paint the edges of a $K_4$ all blue (and the remaining edges are painted red, say - remember that each edge needs to be painted one color or another), then the resulting subgraph consisting of all blue edges is not a 3-regular graph on 9 vertices. The blue graph, which is defined to be the graph induced by exactly the set of blue edges, is a graph consisting of a $K_4$ and 5 isolated vertices, and hence does not contain a 3-regular subgraph on the 9 vertices.

Observe that in $K_9$, each vertex has 8 edges incident to it. Fix a particular vertex $v$, and suppose it has $b(v)$ blue edges and $r(v)$ red edges incident to it. Then $b(v)+r(v)=8$, for each vertex $v$. The author says that in any red-blue coloring of the edges of $K_9$, either $b(v) \ge 4$ or $r(v) \ge 6$ for some vertex $v$. For if that is not the case, then every vertex has at most 3 blue and at most 5 red edges incident to it, and hence every vertex has exactly 3 blue and exactly 5 red edges incident to it (by the requirement $b(v)+r(v)=8$), which is a contradiction since there does not exist a 3-regular graph on 9 vertices (and since there does not exist a 5-regular graph on 9 vertices).