# if a graph G(V,E) is connected $|E|\geq|V|-1$

If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1. It is pretty evident if you think about it but how do i prove it formally?

• By induction. Start with a set $S$ containing any arbitrary vertex $s$. Then add vertex $v$ which is neighbour of some vertex $u \in S$ along with edge $(u,v)$. At each point we will find some vertex and this procedure terminates as graph is connected we will cover all vertices. And at each point we use at least 1 edge so $|E| \ge |V| - 1$. Dec 19 '19 at 11:36

Imagine a process in which you start with the empty graph, and add the edges one by one. Keep track of the number of connected components. In the beginning, there are $$|V|$$ connected components. Each edge you add either belongs inside a connected component, or merges two connected components, and in any case, the number of connected components decreases by at most 1. Hence after adding $$|E|$$ edges, the number of connected components is at least $$|V| - |E|$$. If the graph is connected, $$|V| - |E| \leq 1$$, and so $$|E| \geq |V| - 1$$.