I would really appreciate if someone could check this proof i though. Bare in mind i learned this subject in another language so i apologize in advance for my english.
By Induction:
$G$ connected with n vertex $\implies G$ has at least $n-1$ edges
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 $n \in \mathbb{Z}_{+}$, every connected undirected graph with n vertices has at least $n−1$ edges.
Let's grab G with $n+1$ vertex. If we proceed to delete one vertex $v \in G$, we have these 2 possibilities:
$v$ is not a cut vertex:
Then $G-v$ is connected and has n vertex, then has at least $n-1$ edges. If we proceed to re-add $v$, since $G$ is connected, $g(v) > 0$, then G has at least $n$ edges.
$v$ is a cut vertex:
Then $G-v$ has $K$ components, where $K$ cannot be greater than $g(v)$ since each deleted edges can only generate one more component. Then we proceed to add $e=(u,w)$ with $u \in K_i$ and $w \in K_j$ with $g(v)\geq K\geq j>i$ . This adds up to $g(v)-1$ edges to $G-v$. Now $G-v + edges$ is connected, then it has at least $n-1$ edges. $G-v$ has at least $n-1-(g(v)-1)$ edges, if we re-add $v$, we add $g(v)$ edges, then $G$ has at least $n$ edges.
Thank you very much in advance
Best Answer
This is a nice proof, and I believe it's basically correct. I had to guess what you meant at one point, though:
This sounds like you're adding either one such $e$, or all of them, but from the structure of the proof it seems that what you mean is something more like:
(Also you should perhaps introduce the notation $K_i$ for the components.)