Alright. So the correct answer is the third one,

2^n. A graph of n vertices has essentially 2^n

cut, so there's an exponential number of cuts there's a lot of them.

So why is this true? Well, in effect you can imagine making a

binary decision for each of the n vertices.

They either go into A. What were they going to be?

So n binary decisions results in 2^n different outcomes.

Now why is this slightly incorrect? Well, in fact, a cut has to have two

non-empty sets. A is not allowed to be empty,

B is not allowed to be empty, so that rules out two of the

possibilities. So actually, strictly speaking, it's 2^n

- 1 different cuts of a graph. So what we're going to do next is we're

going to state and prove three easy facts about cuts in graphs.

Once we have these three easy facts, we will be able to prove the claim at the

beginning of this video, namely the Prim's Algorithm always

outputs a spanning tree. The first of these three properties about

cuts, I'm going to call the empty cuts lemma.

The point of the empty cut lemma is to give us a characterization that is a new

way of saying when a graph is connected. So in particular, I'm going to phrase in

terms of a graph not connected. And the claim is that a graph is not

connected if and only if we can find a cut of the graph that has no edges

crossing it. So remember how we defined a graph being

connected, that means for any two vertices in the

graph we can find a path in the graph from one vertex to the other.

So what we're saying is that being not connected,

that is, there existing a pair of vertices with no path between them is

equivalent to there being a cut with no crossing edges.

So let's go ahead and prove this real quick.

So as an if and only if statement, really this proof, we have to do in two

parts. First, we have to prove that assuming the

first statement, we can derive the second.

Then we have to show that assuming the second statement, we can derive the

first. I think the easier direction is to assume

the right-hand side and then derive the left-hand side.

So let's start with that one. That is, consider a graph G so that

there's a cut, A, B with no edges of G crossing this cut.

The plan is to exhibit a pair of vertices that do not have a path between them,

there, thereby certifying that the graph is not connected.

So, it's pretty easy to figure out which pair of vertices we should look at,

just take one vertex from each side of the cut which has no crossing edges.

So why is it that there's no path from U to V in the graph G?

Well the path from U to V would surely have to cross the cuts, A, B, but there's

no edges available for crossing the cut. So therefore, this path from U to V

cannot exist. So that completes the first part of the

proof. We assume the right-hand side, we derive the left-hand side,

now we start all over again, but we assume the left-hand side and we have to

prove the right-hand side. So by virtue of, by the assumption that

the graph is not connected, there has to exist a pair of verticies U and V that

have no path between them. We are now responsible for exhibiting

some cut A, B such that no edges of the graph G crossing.

So where are we going to get these sets capital A and capital B from?

Well, here is the trick, which is going to make the proof go really nicely.

We define the set of verticies of capital A to be those reachable from U in the

graph G. Another way to think about this is that

capital A is simply used connected components in the sense that we discussed

in part 1 of the course. Now because we want to cut and a cut is

our partition, we better well put in the group, capital B, all of the verticies

that are not in A. If you like, this is all of the connected

components other than the one that contains U.

Note that by definition, U is in capital A,

certainly U is reachable from itself. And by assumption, V and U are not

reachable from each other, so V is going to be in capital B.

So neither of these sets is non-empty. This is indeed a bonafide cut of the

graph G. All that remains is to notice that there

are no crossing edges across this cut. And why is that true?

Well, if there was an edge crossing the cut A, B with one endpoint in A, one

endpoint in B. Well, by definition, there are paths from U to everything else in A,

so if there is any edge sticking out of A, that would give us a path to some

vertex in B. But, B definition of vertices not

reachable from capital A, so that's a contradiction.

So again, the point is that if there were edges crossing this cut, then we can

expand A and make it even bigger. So therefore, there aren't any edges

crossing the cut. The cut is empty, that's what we needed

to prove. Assuming the graph was disconnected, we

have exhibited a cut, A, B with no crossing edges.

So that wraps up of the first of our three facts, and in fact, the most

difficult of our three facts about cuts in graphs.

And again,, what did the empty cut lemma say?

It gives us a new way of talking about whether or not a graph is connected.

So it's disconnected if and only if there's an empty cut.

It's connected if and only if there are no empty cuts.

So that's the keypoint from this slide. Let's now knock off the other two facts

we're going to need. The first one I'm going to call the

double crossing lemma. In essence, what the double crossing

lemma says, is that, if a cycle in a graph crosses a cut, then it has to cross

it twice, it cannot cross it only once.

So pictorially, we look at a cut of a graph, so there's the two vertex groups A

and B. By hypothesis, there's some edge E with

one endpoint in each side, and by assumption, this E, this edge E,

participates in some cycle that we're calling capital C.

And if you look at the picture, you realize that the claim in this lemma is

obvious, that, because the cycle has to loop back

on itself, if it has an edge with one endpoint on either side, there has to be

a path connecting the two dots, connecting those two endpoints back to

each other and that path has to cross back for, over this cut A,

B. Indeed, the double crossing lemma is a

special case of a stronger statement which is equally easier to see, which is

that if you take any cut of a graph and you take any cycle you know, it starts

and ends at the same point, then it has to cross this cut an even

number of times. It might cross it 0 times, but it's not

going to cross it once. It could cross it twice.

It could cross it four times, if it crisscrosses back and forth.

It could cross it six times, and so on. But if it crosses it strictly more than 0

times, then it has to cross it at least twice.

That's the point of the double crossing lemma.

So, we'll use this in its own rights later on.

But I'm also, for the moment, interested in easy corollary of the double crossing

lemma. I will call this the lonely cut

corollary. Let me tell you the point of the lonely

cut corollary. In general, in these spanning tree

algorithms, to ensure that we output a spanning tree,

then we have to, in particular, make sure we don't create any cycles.

The point of this corollary is it's a tool to argue that we don't create

cycles. So how can we be sure that an edge

doesn't create cycles? Well, here is a way.

Suppose there's a cut, so we're looking at an edge E, suppose we can identify a

cut A, B so that edge E is the only cut crossing it, it's the lonely edge

crossing this cut. Well then, by the double crossing lemma,

there is no way this thing is in any cycle.

If it were in a cycle and a cross to cut, that cycle would have to cross it again

and it's edge wouldn't be lonely, it would have company.

So if you're lonely on a cut, it mean's you cannot be in a cycle.