# Is "An undirected graph $G(V,E)$ has at least $|V|-|E|$ connected components" a true statement?

I'm taking this Coursera's course on Graph Theory, which is part of a specialization in discrete math for CS, offered by University of California, San Diego: https://www.coursera.org/specializations/discrete-mathematics

In this course they state this theorem:

An undirected graph $$G(V,E)$$ has at least $$|V|-|E|$$ connected components.

With the proviso that if $$|E|>|V|$$, then |V|-|E| will be negative, so, despite of still being true, it will be kind of useless.

Looking for further information on this theorem, I don't find it anywhere else on the web, so I want you guys to tell me if this is a correct theorem, because for some reason I find it "weird".

Start with the empty graph (with $$0$$ connected components), then add your vertices one at a time. At each step the number of connected components goes up by $$1$$. Then add the edges one at a time. At each step the number of connected components goes down by 1 or stays the same. Therefore the lowest it can go is $$|V|-|E|$$.
• You could skip the first half: Any graph with zero edges has $|V|$ connected components. Just the induction on $|E|$ is needed. Jul 22, 2020 at 4:38