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

  • $\begingroup$ Do you know about a spanning tree? $\endgroup$ Jul 4 '15 at 14:43
  • $\begingroup$ 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 $\endgroup$ Jul 4 '15 at 15:14

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

  • $\begingroup$ That sounds a lot better yeah, thanks for that. :) $\endgroup$ Jul 4 '15 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.