Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:
a—–b—–c
with $a$, $b$ and $c$ being vertices, and $\{a,b\}$, $\{b,c\}$ being edges.
Is there some way to prove this logically?
–UPDATE–
Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.
Best Answer
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds. If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.