MathDB

2

Part of 2011 Miklós Schweitzer

Problems(1)

monochromatic connected subgraph

Source: miklos schweitzer 2011 q2

8/29/2021
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.
graph theoryColoring