# Proof that any connected Graph has at least $n-1$ edges

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

• Do you know about a spanning tree? – baharampuri Jul 4 '15 at 14:43
• what's that? i know that a tree has n-1 edges and that if you delete any edge then it wont be connected, but i have to proof that as well – Juan F. Caracciolo Jul 4 '15 at 15:14

## 1 Answer

This is a nice proof, and I believe it's basically correct. I had to guess what you meant at one point, though:

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$.

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:

Then we proceed to add, for each $i$ with $1\le i\lt K\le g(v)$, a new edge $e=(u,w)$ for some $u\in K_i$ and some $w\in K_{i+1}$, for a total of up to $g(v)-1$ new edges.

(Also you should perhaps introduce the notation $K_i$ for the components.)

• That sounds a lot better yeah, thanks for that. :) – Juan F. Caracciolo Jul 4 '15 at 17:33