Show that every simple graph satisfies $m\geq n-k$

Question

Can anybody help me prove this inequality, please? I am not used to proving mathematical statements, so tips and hints are appreciated.

Show that every simple graph $G(V, E)$ satisfies the following inequality $$m\geq n-k$$ where $n = |V|$, $m = |E|$ and $k = \omega(G)$ (that is the number of connected components).

Answer 1

Each component is connected so suppose it has $n_i$ vertices, then it should have at least $n_i-1$ edges (think about a minimal connected acyclic simple graph: it is a tree). Thus the number of edges added over all the components is at least $\sum_{i=1}^k(n_i-1)$. So

$$m \geq \sum_{i=1}^k(n_i-1) =\sum_{i=1}^kn_i -k=n-k,$$ where $n$ is the total number of vertices in the graph.

Answer 2

Start with a graph with just $n$ vertices and no edges. Then $k = n$ since every vertex is its own connected component. Then $$ m = 0 = n - k . $$ Now add the edges one at a time. Each new edge increases the left side by $1$ and may or may not increase $k$, depending on whether it joins two previous components or not. So that new edge may or may not increase the right side.