Problem
COM-B1-M09-P020 Eleven Vertices
#20
★★★☆☆ Level 3 of 5
Prove that a graph on \(11\) vertices in which every vertex has degree at least \(6\) is connected.
In a small component, the degree cannot be large.
If the graph is disconnected, take a component. If its size is at most \(6\), every vertex in it has degree at most \(5\), contradiction. Thus every component must have at least \(7\) vertices. But two such components would contain at least \(14\) vertices, more than \(11\). Therefore there cannot be more than one component, and the graph is connected.
Standard component-size argument.