PUMaC 2013 Individual A Problem 3

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.