Prove that a graph on $n$ vertices with $c$ components has at least $n-c$ edges.

Question

My question is about graph theory. Prove that a graph on $n$ vertices with $c$ components has at least $n-c$ edges.

Answer 1

First we prove that if $c = 1$ (if the graph is connected) we have at least $n - 1$ edges. A simple path with $n$ vertices has $n - 1$ edges, thus it's possible. If $\delta \geq 2$, then we have at least $n$ edges, thus there is a node with $\delta = 1$. use induction on other vertices, so you have at least $n-2$ edges on other vertices of the graph and $n - 1$ edges on all vertices of the graph. Now, we have $c$ connected components with $a_i$ vertices on $i^{th}$ component. thus we have at least $\Sigma_{i = 1}^c (a_i - 1) = n - c$

Answer 2

Suppose your graph has $c$ conected componentes, each with $n_1$, $n_2$, $\ldots$, $n_c$ vertices. Your graph as a whole has $n=n_1+n_2+\ldots+n_c$ vertices. Supose the components are conected by the fewest edges posibles. Any set of $k$ vertices can be conected by just $k-1$ vertices, as in path graphs, $K_{1,k-1}$ bipartite graphs, and so on; so the $i$-th component of your graph can be conected with at least $n_i-1$ edges. The sum of these numbers gives you a lower bound for the number of edges in the whole graph: $$\sum^{c}_{i=1}(n_i-1) =n_1+n_2+\ldots+n_c-c=n-c.$$