Error for graph Theory proof

Question

I am looking for an error in the proof but I am not certain about it. Pretty sure it has something to do with how there is not always a cycle of length 3.

Theorem 1. For every (undirected) graph $G = (V; E)$ without loops, if $|V| \ge 3$ and for every vertex has a degree of at least $2$, there exists a cycle of length $3$.

Proof. We proceed by induction on $|V|$. As a base case, consider $|V| = 3$. For any graph on three vertices, if all vertices have degree $2$, then every vertex is connected to both other vertices. Thus there is always a cycle of length $3$. To prove the inductive step, let $G$ be a graph with $k$ vertices, and construct a new graph $G_0$ on $k + 1$ vertices by adding one new vertex to $G$ and $2$ edges incident to the new vertex. Since $G$ has $k$ vertices, by the inductive hypothesis it has a cycle of length $3$. Thus the graph $G_0$ contains the same cycle of length $3$. This completes the proof.

Answer 1

The way you proceed in your inductive proof doesn't work. Not every graph (of your form) can be constructed in that manner. As in mlo105's answer, $C_4$ is a counterexample: you can't make $C_4$ by starting with a $3$-cycle and adding a vertex and two edges (which is the only kind of $4$-vertex graph your method can create).

In general, when you're doing an inductive proof in graph theory, you usually start with a graph on $k+1$ vertices and somehow reduce it to the case of a graph with $k$ vertices - not the other way around.

Answer 2

The theorem is incorrect. If I give you $C_{4}$, a cycle on four vertices, each vertex has a degree of at least two. However, there is no cycle of length $3$ in $C_{4}$.

Answer 3

You're assuming the new vertex is not on one of the edges of G.