Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/3/d/solution

A vertex with at least neighbours has either a -clique among them, producing with the vertex, or an independent -set among them, producing an induced star with that centre.
For the second assertion put . If either of those two outcomes is absent, the preceding result forces maximum degree at most . In a connected graph of this maximum degree, a ball of radius has at most vertices, using the rough bound on walks at each distance. If the graph has more vertices, some vertex lies at distance at least from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first edges give an induced path of the required length. Thus a sufficiently large connected graph has one of the three listed configurations.

New to topics? Read the docs here!