Given a graph $G$, prove that $m(G) \ge n(G) - c(G) $

Question

Prove that for any given graph $G$, $m(G) \ge n(G) - c(G) $ where $m(G)$ is the number of edges, $n(G)$ is the number of vertices and $c(G)$ is the number of components in $G$.

I am not getting how to prove this, even after trying for last three days. Can anyone please help me with this giving a proof?

Answer 1

You have $n(G)\geq c(G)$, equality holding when $G$ is edgeless.

Now assume $m(G)$ to be a positive integer. Remove an edge to get $G'$. If we assume that $m(G')\geq n(G')-c(G')$ holds, since $m(G)=m(G')+1$ and $n(G)=n(G')$ we get $$m(G)\geq n(G) -(c(G')-1)$$ But since we can at most get one new component when removing an edge (in the case that was a bridge), we have $c(G)\leq c(G')\leq c(G)+1$, or $-(c(G')-1)\geq c(G)$, which leads to the desired inequality.

So you can prove the inequality by induction over the number of edges.

Answer 2

Take the graph $G$ and remove all the edges. You now have zero edges, and equally many vertices and components, so the inequality says $0\geq0$.

Add back the original edges of $G$, one by one. Each edge increases the number of edges by $1$, and either decreases the number of components by $1$ or doesn't change the number of components.

So for each edge added, the LHS increases by $1$, and the RHS possibly increases by $1$. Regardless, the inequality holds for each new edge added, and in particular after adding the last edge, resulting in the original $G$.