MathDB

Let

n \geq 3

be a positive integer. Find the smallest positive real

k

, satisfying the following condition: if

G

is a connected graph with

n

vertices and

m

edges, then it is always possible to delete at most

k(m-\lfloor \frac{n} {2} \rfloor)

edges, so that the resulting graph has a proper vertex coloring with two colors.

10.4