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

Question

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

tkf · Answer

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

Answered by tkf on November 18, 2021

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

One Answer

Add your own answers!

Ask a Question