Suppose by contradiction that the graph is disconnected. At least one connected component, let's call it , would have less than 10 vertices.

The vertices of are only connected to vertices in , so they have at most 9 neighbours.

1) if the cardinality of is at least 2, take and [tex]v[/Math] inside . This leads to a contradiction.

2) if the cardinality of is 1, the cardinality of the complement of is 19 and the degree of vertices in the complement is hence less than 18. Take (in fact [tex]A=\{u\}[/Math] so it is not connected to any other vertex) and outside . Then , and you get another contradiction.