MathDB

There are 10,000 vertices in a graph, with at least one edge coming out of each vertex. Call a set

S{}

of vertices delightful if no two of its vertices are connected by an edge, but any vertex not from

S{}

is connected to at least one vertex from

S{}

. For which smallest

m

is there necessarily a delightful set of at most

m

vertices?

Problem Statement