monochromatic connected subgraph
Source: miklos schweitzer 2011 q2
August 29, 2021
graph theoryColoring
Problem Statement
Suppose that the minimum degree δ(G) of a simple graph G with n vertices is at least 3n / 4. Prove that in any 2-coloring of the edges of G , there is a connected subgraph with at least δ(G) +1 points, all edges of which are of the same color.