We will now prove a simple lower bound on the number of connected components in

terms of the number of nodes in the graph and the number of edges in this graph.

So, the theorem states that for any graph g,

the number of connected components in this graph is

at least its number of nodes minus its number of edges.

So, we will prove this theorem in a minute but now lets consider several special cases.

First of all, if the graph is connected,

then this theorem says that the number of edges in this graph is at least V -1.

At least the number of nodes minus one. Why is that?

We'll assume for the sake of contradictions that the number of edges is at most V-2.

So, it is strictly smaller than V - 1.

But in this case this theorem would give us

that the number of connected components in this graph is at least two.

But this is a contradiction with the fact that the graph is connected.

Recall that the graph is connected,

that if the graph is connected then the number of

connected components in this graph is equal to one.

So another extreme case is when there are no edges in our graph.

So, in this case the number of edges is equal to zero and then in this case the theorem

states that the number of connected components is

at least V and in this case it is actually equal to V,

which makes perfect sense because if there are no edges in the graph

then each node forms a separate connected component.

So, if we have the nodes then we have the connected components.

Finally, let me also remark that

if the number of edges is at least the number of vertices in our graph,

then this theorem is useless,

because the lower bound that it gives is that the number of connected components

is at least some non-positive number is at least zero,

or at least -1 for example,

or at least -2 which is actually obvious,

because the number of components is always non-negative.

Now let's turn to proving this theorem.

So, again what we are going to do is to first remove

all the edges from our graph and then adding them back one by one.

Okay, so, if we remove all the edges then what we have is the nodes.

So, initially we have the connected components and

our goal remember is to prove that the number of

connected components is at least V - E. So,

initially we have the connected components and the quantity V - E is equal to just V,

because E is equal to zero.

So, initially the inequality holds with equality.

Then let's see what happens if we add an edge to our graph,

when we start adding edges.

So, first of all this quantity V-E,

each time when we add an edge it decreases by one.

So E increases by one when we add a new edge,

which means that V - E each time decreases by one.

Now our goal is to understand what happens with the number of components.

So, initially it is equal to V and we

will show that each time when we add a new edge in our graph,

the number of components either stays the same or decreases by one.

So, if we show that each time it either stays the same or decreases by one,

it will prove this theorem. Why is that?

Well, initially we have the number of connected components

on one end and we have this quantity V - E on the other hand.

Each time when we introduce a new edge,

this quantity decreases by one and this quantity either

decreases by one or stays the same.

So, in the process what happens is the following;

this one always decreases,

and this one sometimes decreases and sometimes stays the same.

So, this one decreases faster than that one.

And this actually proves that the number of

connected components is always at least V - E. So,

what remains to be shown is that each time when we introduce a new edge,

the number of connected components either stays the same or decreases by one.

Well, consider these two cases.

One is that a new edge which is shown here in orange and brown connects

two nodes from different connected components and this

is exactly the case when the number of connected components decreases by one.

So, in this case,

before adding this edge we had the following two connected components,

and when we add the new edge these two connected components actually merge into one.

So the number of connected components decreases by one.

On the other hand,

if the new edge joins two nodes that actually belong to the same connected component,

then the number of connected components do not change.

So, we initially had

these two connected components and when we add this brown edge the number,

they just stay the same because the new edge

just joins two nodes of the same connected component.

And this finally proves our lower bound.