I would appreciate it if anyone can verify my proof. It is a proof by induction, but I attempt to reason things out rather than using a purely mathematical approach, in a similar vein to many other graph theory proofs I have come across.
Base case: A graph with 1 vertex is defined to be connected. Clearly it has at least 0 edges.
Inductive case: Assume that for some $k \in \mathbb Z^+$, every connected undirected graph with $k$ vertices has at least $k-1$ edges. If we select any of such a graph, and introduce a single vertex $k'
$, then there are now $k+1$ vertices. We know that there was a path between every two distinct vertices in the old graph. To maintain connectivity, we must join this new vertex $k'$ to $at$ $least$ $one$ of the $k$ vertices in the old graph. Suppose we join $k'$ to a vertex $v$ in the old graph. Then there will be a path from $k'$ to each of the $k$ vertices in the old graph $via$ $v$. Thus the new graph is connected, and it has $k+1$ vertices and $k$ edges.
Therefore $\forall$ $n\in\mathbb Z^+$, every connected undirected graph with $n$ vertices has at least $n-1$ edges.
Best Answer
I'm sorry, but your proof is incomplete; you fell into the so-called "induction trap".
For the induction step, you assume that any connected graph with $k$ vertices has at least $k-1$ edges; and you want to prove that any connected graph $G$ with $k+1$ vertices has at least $k$ edges. In trying to prove this, you assume that $G$ was obtained by adding a new vertex (which you confusingly call $k'$) to a connected graph with $k$ vertices. But you have not justified this assumption.
To justify your argument, you would have to show that every connected graph with $k+1$ vertices can be obtained by adding a vertex (and some edges) to some connected graph with $k$ vertices. In other words, you have to show that, given any connected graph with $k+1$ vertices, you can find a vertex whose deletion results in a connected graph. This is true, but requires a proof. (Well, it's true for finite graphs, which is what we're talking about. In a connected infinite graph, it's possible that deleting any vertex disconnects it.)
For an alternative approach, you can delete an arbitrary vertex $v$ from a $k$-vertex graph $G$, without worrying about whether $G-v$ is connected or not; you then apply the induction hypothesis to each connected component of $G-v$, however many there may be. In this approach, you have to use the style of induction where you prove the statement for $k$ assuming that it holds for all numbers smaller than $k$.