Let $ G$ be a graph with $ 2n$ vertexes and $ 2n(n-1)$ edges.If we color some edge to red,then vertexes,which are connected by this edge,must be colored to red too. But not necessary that all edges from the red vertex are red. Prove that it is possible to color some vertexes and edges in $ G$,such that all red vertexes has exactly $ n$ red edges.
Problem
Source: SRMC 2008
Tags: graph, Graph coloring, Coloring, combinatorics
Pathological
09.09.2019 03:17
Call a pair of the $2n$ vertices a non-edge if there is no edge between them. Observe that there are $\binom{2n}{2} - (2n^2 - 2n) = n$ non-edges. We consider two cases. Case 1. There exist two non-edges sharing a vertex. Call that vertex $v_1$, and consider the following operation. Start by marking $v_1$ green. At any point, we say that a non-edge is banged if one of its vertices is green. The operation then proceeds by taking a non-edge which isn't yet banged, and marking one of its vertices green. If all non-edges are banged, continue marking random vertices green until a total of $n-1$ vertices are green. Notice that since each marking bangs at least one edge, and the first marking bangs at least two, at the end of this operation $n-1$ vertices are green and all edges are banged. It suffices just to color red the $n+1$ other vertices and all edges between them. Case 2. Any two non-edges don't share a vertex. Then, we can label the vertices $v_1, v_2, \cdots, v_{2n}$ so that $(v_i, v_{i+n})$ is a non-edge for each $1 \le i \le n.$ Now, simply color every vertex red, and then color red the edges connecting vertices in $\{v_1, v_2, \cdots, v_n\}$, the edges connecting vertices in $\{v_{n+1}, v_{n+2}, \cdots, v_{2n}\}$, and the edges $v_1 v_{n+2}, v_2 v_{n+3}, \cdots, v_{n-1} v_{2n}, v_n v_{n+1}.$ $\square$