Problem
COM-B1-M09-P017 Minimum Degree \(3\)
#17
★★★☆☆ Level 3 of 5
Prove that a graph on \(6\) vertices in which every vertex has degree at least \(3\) is necessarily connected.
If the graph is disconnected, consider a component with at most \(3\) vertices.
If the graph is disconnected, its vertices split into at least two components. One component has at most \(3\) vertices. Inside such a component, any vertex can be connected to at most \(2\) other vertices, so its degree is at most \(2\). This contradicts the condition that all degrees are at least \(3\).
Simple but important method for proving connectedness.