1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$ Dec 19 '19 at 11:36
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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