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!