I've got this problem from a textbook and couldn't find out what the problem should be here.
Suppose we want to prove that if $G = (V,E)$ is a connected graph with
$|V| = |E| + 1$, then it is a tree.
What is wrong with the following proof?
We already assume that the considered graph is connected, so all we need
to prove is that it has no cycle. We proceed by induction on the number
of vertices. For $|V| = 1$, we have a single vertex and no edge, and the
statement holds.
So assume the implication holds for any graph $G = (V, E)$ on $n$ vertices. We want to prove it also for a graph $G' = (V', E')$ arising from $G$ by adding a new vertex. In order that the assumption $|V'| = |E'|+1$ holds for $G'$, we must also add one new edge, and because we assume $G'$ is connected, this new edge must connect the new vertex to some vertex in $V$. Hence the new vertex has degree $1$ and so it cannot be contained in a cycle. And because $G$ has no cycle (by the inductive hypothesis), we get that neither does $G'$ have a cycle, which finishes the induction step.
Best Answer
Suppose we change the statement we're trying to prove: replace "connected graph $G=(V,E)$ with $|V|=|E|+1$" with "graph $G=(V,E)$ with no isolated vertices amd $|V|=|E|+1$". (Also, to give us a nice basis for the induction, let's just consider graphs with at least $2$ vertices.)
The "proof" seems to work the same as before. The only place we used connectedness was when we said "because we assume $G'$ is connected, this new edge must connect the new vertex to some vertex in $V$." But we can just as well say "because we assume $G'$ has no isolated vertices, this new edge must connect the new vertex to some vertex in $V$."
But the modified statement is false: the graph $G=K_3+K_2$ has $4$ edges and $5$ vertices, has no isolated vertices, and is not a tree. So what went wrong??
In a proof by induction on the number of vertices, going from $n=4$ to $n=5$ means that we assume that the statement holds for every $4$-vertex graph, and we have to prove it for every $5$-vertex graph. Note that we tacitly assumed that every $5$-vertex graph which satisfies the hypotheses can be obtained by adding a vertex to some $4$-vertex graph which satisfies the hypotheses. For the modified statement this is false; the graph $G=K_3+K_2$ can not be obtained by adding a vertex to a graph with $4$ vertices and $3$ edges and no isolates.
Going back to the original statement, a connected graph with $5$ vertices and $4$ edges can be obtained by adding a vertex and an edge to a connected graph with $4$ vertices and $3$ edges (because it is a tree, so it has a leaf, and removing a leaf gets us the desired $4$-vertex graph), but that needs to be shown.
To repair the proof, we could say: Let $G$ be any connected graph with $n+1$ vertices and $n$ edges. Since $G$ has more vertices than edges, its average degree is less than two, so it has a vertex $v$ of degree less than two. The degree can't be zero (since $G$ is connected), so $v$ has degree one. Then the graph $G'=G-v$ has $n$ vertices and $n-1$ edges, and $G'$ is connected, because you can't disconnect a connected graph by removing a vertex of degree one.