Show that any connected graph $G$ satisfies $\lvert E(G)\rvert \geq \lvert V(G)\rvert -1 $ by induction on the number of edges.
My attempt:
- Base Case: For any connected graph $G$ let number of vertices $= 1$ so $0 \geq 1-1$ which is true.
- Now i'm not really sure what to do here.
Try removing a vertex. How many edges are left? How many disappeared?
If the graph that remains after removing the vertex is connected, then by induction there are at least $|V(G)|-2$ edges remaining since there is a connected graph with $|V(G)|-1$ vertices, and we would have had to remove at least one edge in removing our vertex, so $G$ has at least $|V(G)|-1$ edges.
If it is not connected, it is the disjoint union of some number of connected components, say $k$. By induction, the sums of the number of edges in these remaining components is at least $(|V(G)|-1)-k$. In order for $k$ components to have been created by removing the vertex, we would have had to remove at least $k$ edges. Thus the original graph has at least $(|V(G)|-1)-k+k=|V(G)|-1$ edges.