This question already has an answer here:

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, user91500 Apr 20 '17 at 5:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – JMoravitz Apr 20 '17 at 1:14

You can prove it with induction. For 1 and 2 vertices it is trivial.

Then if you add a new vertice to the graph, you have to connect this vertice to the rest, to make the graph connected. Thus, also the required edge number increases with 1.

Into the other direction, that it is always enough, you can use a constructive example: a linear graph.


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