Let’s prove the following statement: every graph without isolated vertices is connected.
Proof We use the induction on the number of vertices. Clearly the statement is true for graphs with \(2\) vertices. Now, assume we have proven the statement for graphs with up to \(n\) vertices.
Take a graph with \(n\) vertices by induction hypothesis it must be connected. Let’s add a non-isolated vertex to it. As this vertex is not isolated, it is connected to one of the other \(n\) vertices. But then the whole graph of \(n+1\) vertices is connected!