# A connected graph with n vertices has at least n-1 edges [duplicate]

Prove that a connected graph with n vertices has at least $n-1$ edges.

Prove by M.I: we know that deg(v) $\ge1$ for all vertices v, since the graph is connected. Then either deg(v)$\ge 2$ for all v, or there exists one vertex with degree 1. How do I actually show this desired result. Any help is appreciated.

Step 1: Let n=1, then there are 1-1=0 edges. True

Step 2: Show that a connected graph with n+1 vertices, it has n+1-1 edges. I need help on this part. Do I need to use the summation of degree (v)= 2 times the number of edges?

## marked as duplicate by Misha Lavrov, lulu, JMoravitz, Jonas Meyer, user91500Apr 20 '17 at 5:35

• As an aside, "Then either deg(v)$\geq$2 for all v, or there exists one vertex with degree 1". You are able to have a connected graph with two vertices of degree one... consider a path. In general, you are able to have many vertices of degree one. Consider a star. – JMoravitz Apr 20 '17 at 1:14