let G be a graph with 2n vertexes and 2n(n-1) edges, we have red color
Source: SRMC 2008
August 31, 2018
graphGraph coloringColoringcombinatorics
Problem Statement
Let be a graph with vertexes and 2n(n\minus{}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 ,such that all red vertexes has exactly red edges.