MathDB

A graph consists of a set of vertices, some of which are connected by (undirected) edges. A star of a graph is a set of edges with a common endpoint. A matching of a graph is a set of edges such that no two have a common endpoint. Show that if the number of edges of a graph

G

is larger than

2(k-1)^2

, then

G

contains a matching of size

k

or a star of size

k

Problem Statement