0
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ You could skip the first half: Any graph with zero edges has $|V|$ connected components. Just the induction on $|E|$ is needed. $\endgroup$
    – aschepler
    Jul 22, 2020 at 4:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .