Tip:
Highlight text to annotate it
X
So, we are in this course, we are going to learn Graph theory. For this course, I will
be using the following books one is a Graph theory by Reinhard Diestel, and other one
introduction to Graph theory by Douglas West; in the Graph theory by Bondy and Murty and
Bollabas modern Graph theory.
So, there are many other books in Graph theory. So, you can use those books also if you like,
but most of the time I will be taking material from this books. To begin with, let us consider
the question, what is a Graph? Is say it is a triple, the vertex set V of G, the edge
set E of G and a relation which associates to each edge two vertices; these two vertices
are called the end points of the edge; to an edge we associates two vertices which are
called an end points of its edge.
So, it is a much easier to represent a Graph by a drawing; so, it can be like this say.
Let us say I am drawing, if these vertex sets, vertex sets; this is 1, 2, 3, 4, 5. So 1,
2, 3, 4, 5 of the set of vertices, and the edges can be say e 1, e 2, e 3, e 4, e 5 say.
So here, the edge e 1 is associated with the two vertices 1 and 5. It is call the end points
of the edge e 1, the edge e 2 is associated with the 5 and 2, the end points of e 2 like
that. Now, what kind of edges is possible? So, it is not necessary that the two vertices
associated with an edge the end points or distinct to vertices it can be like this,
the two vertices associated with this edge say e 6 is 2 and 2.
So, it is called a loop, because both the end points are same. Now, it is also possible
that there are many edges, which are associated to the same pair of vertices. For instance
it is possible to have several edges say e 2, say e 7, e 8; such that the two vertices
associated with them are same, the same 5 and 2. So, then we call this is a multiple
edges here between this two vertices. The when we denote have any loop or multiple edge
in a Graph, then we say that the Graph is a simple Graph. It is also possible that our
vertex set is infinite, the edge set is infinite, but if you assume that both the vertex set
and the edge set is finite. Then we say that it is is a finite Graph.
Usually in this course, most of the time we will be taking about finite Graphs, and a
simple Graphs, if at all we are talking about non-simple Graphs will be explicitly mentioning
that or if we talk about infinite Graph will be explicitly mentioning that.
Now, let us consider some example Graphs which are some simple simple Graphs. The first one
is complete Graph; what is a complete Graph? Where corresponding to each possible pair
of vertices, we have an edge.
So, for for instance, let us consider the simplest example: The it is let let it be
the vertex set be a single turn which is one, then there is no pair of vertices then itself
is a complete Graph, no edge right. So, we are talking about simple Graphs there.
And then say suppose there are two vertices -- 1 and 2 then there is only one pair. So,
this is a complete Graph, this is called k 2 - complete Graph on two vertices. So, the
suppose there are 3 vertices. Then there are three pairs one is like this, this is other,
third one is this; this is 1, 2, 3. This is the complete Graph 1, 3 vertices; the how
will the complete Graph on 4 vertices look like. So, I will draw four nodes 1, 2, 3,
4. So, I put all the possible edges. So, because there are 6 pairs here have to add all the
6 this is the complete Graph on this thing.
So, when I say complete Graph on n vertices, there are n choose 2 pairs n choose 2 pairs,
say if V of G the the vertex set of G is called V of G, if this is equal to n then n choose
2 pairs of vertices right are possible. Corresponding to each pair, we have to have an edge; then
it is called a complete Graph on n vertices. The notation for the complete Graph on n vertices
is K n.
Now, the next thing is two notions: Sub graphs, induced Sub Graph. So, given a Graph G, we
say that another Graph H is a Sub Graph of H. If the vertex set of H is a subset of the
vertex set of G that is what a we mention. So, V of H is a subset of V of G, and the
edge set of H is a subset of the edge set of G. Thus next statement is just to say that
the edge set means we are not just naming, we are just using the same name, but the assignment
of a vertices to the each edge is the same G and H. For instance rather than explaining
like this, it is better to draw a Graph ensure.
So, for instance let us consider this simple example.
This is called as cycle cycle Graph C n. So, the cycle this is called a cycle Graph. The
cycle on n vertices C n. And. So, suppose we collect these vertices using red, let say
these vertices and then take some of the edges here; so, this one, this one. So, here the
vertex set these red color vertices now is a subset of the vertex set of the original
Graph C n, and the edge set is also a subset of the original Graph C n. So, then this is
a this looks like this; this is a Sub Graph of the original Graph.
Let us may be you can consider little more complicated, some little more complicated
figure. So, let us say consider this Graph. Now, if I consider these vertices. So, and
this edges, this is a sub Graph. So, this black edges and these vertices form a Sub
Graph of this big Graph; and so, and then the next is a notion called induced Sub Graph.
What is an induced Sub Graph? So, the induced Sub Graph means, if we select few a vertices
- a subset of G and then look at the edge set for instance we can consider our earlier
earlier example. So, this was here we selected the vertex set,
and this is what we got is something like this red red, this is called a path Graph
say. So, something like this is a path Graph on three vertices, and sees when I consider
these vertices all the edges of C n, the original Graph which have both end points in the selected
collection of vertices, is there in the sub Graph also. Then this is called an induced
Sub Graph.
So, in the next for next example let us more a clearer. Here I have selected this vertex,
this vertex, this vertex, and this vertex. But the edges are only this, this, this, and
this. This edge is not selected. So, this is not an induced Sub Graph; to make it an
induced Sub Graph, we have to add this also. So, this is an induced Sub Graph.
Now, the next one is a connected Graph - the notion of a connected Graph. We say that a
Graph is connected if each pair of vertices belongs to a path.
That means, suppose we can consider this simple Graph. So, here there are 6 vertices in this
Graph. So 1, 2, 3, 4, 5, 6. So, between 1 and 2 there is a path, between 4 and 6 there
is a path, but suppose I consider the vertex 1 and the vertex 4, then I do not see any
path -path means, if I start from here and then follow an edge, and then I cannot reach
here. So, this is a disconnected graph. Now, how do I make for instance if, this has to
be became a connected graph. So, for instance I can put this edge here. So, then this becomes
a connected graph; that means, if I start from any vertex, I can reach any other vertex
using a path, path is like this. So, this is the notion of the connected.
In this lecture, I am not going to tell all the definitions as in a text book, because
that will be very boring for a class. So, what I will do is I will introduce the notions
which are necessary to understand the things as and when it is required. But it also advisable
that, this students can go through the introductory chapter of one of these text books which I
mentioned earlier say, the the once which I mentioned earlier for instance this one.
So, this any of these four books ,we can see the introductory chapter explaining many the
commonly used definitions, words are the terminology extra.
So, one can read that, but otherwise anyway I will be explaining that terms which I use
as, and when it is required.
Now, one word which we always use as isomorphism. This is for instance, we can we sometimes
say that there is, a path on 5 vertices is a sub Graph of G, is essentially a path on
5 vertices is isomorphic to Sub Graph of the given Graph like that. So, therefore, it is
I will just mention this word. So, an isomorphism from a simple Graph G to
a simple Graph H is a Bijection, such that whenever u and u, v is an edge of G, then
the corresponding pair f of u comma f of v is an edge of H. So, to understand this thing
we can take an example.
So, here let us let us draw a Graph. So, this is our G here; 1, 2, 3, 4. So, now, consider
another Graph like this. So, looks very different, but then we say that these two Graphs are
isomorphic. Because it it will name it like this a, b, c, d. Because I can map vertex.
So, the function f will map 1 to a. So, that is one will be map to, a a to can be map to
can be map to b, 3 can be map to, c and 4 can be map to d, this is a function f. So,
as we wanted. So, whenever there is an edge; that means, 1, 4 is an edge. So, the corresponding
vertices a and d, between a and d there is an edge. So, we say that if. So, for similarly
1, 3 there is no edge. So, between a and c the corresponding vertices here, a and c there
is no edge here. So, thus therefore, we say that there is an
isomorphic. These two Graphs are isomorphic. Essentially; that means, we have a same Graphs,
but maybe we have drawn a differently something like that. And so we can take another example
for instance.
So, so let us take this Graph.
Right 1, 2, 3, 4. So, another Graph I can draw like this; let us this be G 1, and then
let let me draw another Graph this is like this. So, first look these two since to be
very different Graphs, but in fact this one can be map to these things a 1. So, this correspond
to this say 4 can be map to this one, say and 3 can be map to this thing; another this
triangle comes here, and these two can be map to this. sorry you can be map to this.
This 2, 2 1, 2 1 there is an edge; 2 3, 2 3, there is an edge, 2 4 this edge you can
see. So, you can see that, whenever there is an
edge between say I and J here, the corresponding edge is present here also; otherwise, if there
is a no edge then that edge there. So, this is the notion of isomorphism.
So, next let us say. So, too... So we can consider a Graph, and then if we can ask this
question is there a Sub Graph is there a Sub Graph for G, which is isomorphic to a cycle
cycle on 3 vertices, 4 vertices, 5 vertices; if there is no Sub Graph for G which is isomorphic
to a cycle, then we say that it is an acyclic Graph.
So, a Graph without any cycle; that means, in it in a cyclic Graph is called forest.
So, how will a forest look like? So, it may look like say see see that is know we can
put a cycle right, this may look like this. So, this is a forest. Suppose it is a connected
Graph also, here you see this is acyclic, but not connected this is disconnected Graph,
but if it is a connected Graph also then we say that it is a tree. So, how do you for
instance what kind of edges I can put to make this Graph connected for instance I can add
say this edge, and say this edge. So, now this is this is become a tree. Now,
if I for instance if I add this edge then what will happen is, this acyclic form, then
it form be a tree. Neither will be a tree nor will be a will it be a forest. So, I cannot
put that. So, this is the notion of tree.
The next notion I want as that is a Bipartite Graph, we say that a Graph G is bipartite;
if it is vertex set is the union of two disjoint, possibly empty independence sets called a
partite set of G. So, a subset... So, what do I mean by independent sets. If I if I consider
a subset of a Graph, and look at the induced Sub Graph of it. And if you any edge in it,
then it is called an independence set of that Graph.
So, for instance we can consider in this Graph for instance, we can consider this say, say
some of these vertices say this one, this one, this one, this one. So, these 4 vertices.
So, if I consider the induced Sub Graph on these 4 vertices will just get something like
this right, right they want any edge on it right. So, therefore, this this will be an
empty sorry this is this is an independent set this is called an independent set of this.
So, we say that the Graph G is bipartite, if we can partition the vertex set of G into
two groups; such that, the each of this collection group is inducing and independent set in the
Graph.
So, we can take some simple examples like. For instance I can consider a cycle. So, is
this a sorry. So, let say consider this cycle, this cycle. So, now, how do I partition it
into two collections, such that such that each collection induces and independent set.
For instance, I can say this I will put it in one part, this I will put it in same part
this; so, I will put it in the same part. And the other one set this, this and this
I will put in the other part. So, these black vertices form induce and independence set
in these Graphs; similarly, these induce and independent sets in this Graph.
So, every edge in this Graph is going from a red vertex in the black vertex. So, for
instance you could have grouped. So, if I number it has 1, 2, 3, 4, 5, 6. I could have
placed 1, 3 and 5 my black vertices on this side. And the red vertices say 2, 4 sorry;
2, 4 and 6 on this side on the edges will be1, 2, 3, 4, 5, 6, 1. So, the edges always
going from one side to the other. So, this is one way of viewing the Bipartite Graph.
So, a Graph is a bipartite Graph if I do these things right in a Graph. So, is it possible
that any Graph is Bipartite.
So let us consider some simple examples like. So, consider a tree. So, this is a tree is
this a bipartite Graph for instance simple; yeah this is a bipartite Graph, because we
can place say this in one side, and then immediate children of that can be placed in the other
side right in the other part; and then the children of this can be placed in the other
part like this. So for instance, if you want see it in these two part form. So, 1, 2, 3,
4, 5 then I can place one here, and then 2 and 3 should go to the other side, 2 and 3
should go to the other side, these 2 vertices; and 4 and 5, so it neighbors of two should
come to this side 4 and 5. So you can see that, so by extending this argument you can
see that any tree can be placed like this, on 2 2 sides.
So, without any edge appearing in this side or without any edge appearing in this side
right. So, all the edges will go from one side to other; the trees are like that, trees
are Bipartite Graphs. Now so we show that, some cycles are Bipartite; it is true that
every cycle is a bipartite Graph.
So, we can consider this cycle for instance simpler cycle the triangle 3, it is called
a triangle. So, or 3 cycles C 3 is this a bipartite Graph. So, suppose this is a bipartite
Graph, then we should be able to place the vertices in two groups, in such a way that
the edges go from one side to the other. So, let say one is placed in this thing without
lose of generality this side. Now, if one is placed here, this 3 and 2 should be on
the other side. 2 and 3 should be on the other side, because there is an edge between 1 and
3, 1 and 2, but then between 3 and 2, there is an edge it has to come here. So, this will
become a problem right. So, this will be flop. So therefore, this triangle cannot be a bipartite
Graph. So, what kind of cycles are not Bipartite. So, with some thought we can see that, every
even cycle can be place like this, but the odd cycles cannot place like this. So, you
can try to place 1, 2, 3, 4, 5, 6, 7 vertex. So, this 7 vertex C 7 can this be placed like
this. So, it is not possible; for instance if I place it in the first part, and then
I will have to place this and this in the other part, and if I then I will have to place
this in the first part, and then I will have to place this in the red part, this also has
to be in the red part, there is an edge between these two red parts. So, therefore, these
cannot be a bipartite Graph. So, this is part a bipartite Graph is.
Now, we will and now, because the triangle the K 3 is not a bipartite Graph. So, we can
we know that no complete Graph K n, where n greater than equal to 3 is a bipartite Graph.
Because if the complete Graph on 3 vertices itself cannot be placed like that, then more
complete Graph on more number of vertices cannot be place like that.
So, what about, but then there is a notion of a complete Bipartite Graph. What is a complete
Bipartite Graph? So, complete bipartite Graph means... So, we should be able to group the
vertices into two groups such that. So, so they... So, let say this is A, and this is
B, and then whenever I have an edge x is vertex here, and whenever I have vertex y here, then
they will be an edge here. In other words, all the pairs with one of
one from A and one from B will form an edge. So, usually we will we will show it like putting.
So, say thick sorry. So, we can show it like a selecting. So, like these all the edges
are there. So, we can we can indicated like this, all the all the possible edges between
A and B are there; this is called a complete Bipartite Graph. So, notation for instance
suppose there are m vertices in this A side, n vertices in the this B side; then we will
call it K n m, this is the notation for that. Remember the complete Bipartite Graph is K
n with n vertices, here this K n m - n for the number of vertices here sorry. So, let
me say K m n or yes as we wish K m n.
So, this is a complete bipartite Graph.
And from known I will introduce some concepts, some concepts about Graphs. The first one
is called a vertex cover. So, what is a vertex cover? The set S of the vertex set of G S
subset of V of G is a vertex cover of G, if every edge of G is incident with a vertex
in S. A vertex cover of the minimum cardinality called a minimum vertex cover.
So, let us take an example to explain this. So, so consider this Graph - simple Graph.
Say simple Graph, now I am asking for a collection of vertices such that, every edge has one
of the end points in this set. For instance, let me show an example. So, so I will let
me take this vertex, and this vertex, and this vertex. Now, you take any edge. Suppose,
this edge; it is one red end point. So, this edge it is one of the in fact, both the end
points are red. Here another edge, it is one of the end points as red. So, another edge,
so one end point is red, and another edge one end point is red.
So, every edge is such that, it has at least one end point as red. So, then these 3 vertices,
the set of these 3 vertices, red vertices called a vertex cover of this Graph. So, interesting
way of explaining it is suppose you consider museum. So, museum say let me draw say something
like this.
So, these are the corridor where the museum articles are displayed. So, museum art gallery
are something like that. So, may be...
So, here we have to place some entries; such that for instance if if a guard sits here,
a sentry sits here. He can see this corridor, this corridor, and make sure that the people
are not stealing things from the art gallery. So, this these three base we can watch watch
for, but under the other hand he cannot see what is happening here. So, similarly if something
is some theft is happening here, he cannot see that. So, you may have to place another
person here. So, that you can watch here, watch here. So, he watches this and this.
So, who will watch this, this only may have to place one here.
So, if you placed one sentry here, one sentry here, and one sentry here. They can together
watch the entire museum. So, of theft will happen right. So, here this problem can be
modeled as a Graph problem. So, as you can see. So, here this will be converted to a
small vertex, and then this will be converted to a vertex this, this, this. All the corners
will be converted to a vertex. So, I will say I can draw a Graph like this based on
this, and it will look like this. So, this is the... So, I have formed Graph from this
art gallery. So, where these are the places where we can
possibly place these sentries. So, there is no point placing is a sentry here, he can
only see here. So, if we see here, he can see anyway this. So, these are the corners
and then these are the corridors along which people move and the articles are displayed.
Now, the question is the same as asking what a minimum vertex cover here, why minimum because
we want the minimum number of is sentries to placed to minimize the cost.
So, see so here, if we place as we so, we can place one here. So, these we can say select
this vertex. So, as a position for sentry placing the sentry, and our we can select
this one. So, this will say together this one, these two is a covered this is covered,
but now this is not protected. So, if I if I place one here, then you can covered still
it will be this will not be covered. So therefore, I can place one here; these three this thing.
So, so the minimum number of guards we have to place. So that, the entire museum will
be watched is the same as the the minimum number of vertices, that we have to be selected,
such that every edge has at least one end point in it. So, this is called a minimum
vertex cover. So, the vertex cover is just a collection
of vertices such that every edge has at least one end point in it; minimum vertex cover
is the one which minimizes that cardinality; that means, we want the smallest vertex cover.
Now to get familiar with the what is a vertex cover, we can ask the some some take some
examples and see, what are the what is the cardinality of the minimum vertex cover in
those Graphs. For instance our first Graph, the complete Graph K n what is a cardinality
of the minimum vertex cover in a complete Graph.
So, it is... So, so easy to say that for instance if there are ten vertices, and if I just take
one vertex, this one vertex cannot cover all the edges right. So, how many we will need
to cover.
So, with some thought we can understand that we will have to take. So, if we take n minus
1 vertices from the, from the n vertices. Then we can cover all the edges; cover the
edges means. So, the all the edges will have at least one end point in it. For instance,
so let us say this complete Graph, this is the K for the complete Graph on four vertices.
Now, if I take say if I take this one, this one, and this one; then you see that all the
edges are covered, it is very easy to verify. But now the question is it possible that.
So, the from this thing what do we get, there exist vertex cover of cardinality 3; that
means, say n minus 1 for a complete Graph on n vertices, but is it possible that we
can cover all the edges of a complete Graph on n vertices by less than n minus 1, what
if it is possible some clever way of selection. But some thought will reveal to us that; it
is not possible, because suppose we can do that suppose we can do that, using just n
minus 2.
Suppose suppose there is a vertex cover with n minus 2 vertices, then there are 2 vertices
say let us say x and y in the Graph, such that it is not in this vertex cover. Because
we have in the vertex cover, we have only n minus 2 vertices, there are 2 more vertices
let x and y be the two vertices. So, because it is a complete Graph between x and y, we
do have an edge. Neither x nor y is in the vertex cover we have selected. So, who is
covering this edge right? So therefore, if we have only n minus 2 vertices
in the set we have selected, it cannot be a vertex cover. So, the number of vertices
in a the vertex cover of complete Graph is, at least n minus 1 and its n minus 1 is enough.
Therefore, for complete Graph the cardinality the minimum vertex cover is n minus 1.
Now, let us consider another example. So, what about a complete Graph on complete Graph
K m n on, so with m vertices on one side, complete bipartite; there is not complete
Graph.
So, so we... So, that it is like this for instance m vertices here, n vertices here.
So, is a bipartite Graph, this is an independence set, this is an independent set nothing inside,
it no edges there. And then for instance, we we can say it look like this. So, all the
edges of there in here, all the edges are there from this to this right. We have to
cover all these edges. So, what is the minimum? So, if you if you see that suppose if I take
all these vertices, then definitely it will cover all these edges, because every edge
has to have at least one end point in this side or if I take all the vertices from this
side, that is also enough. So, since we are looking for a minimum vertex
cover. So, we will take this smaller side, if m is less than equal to n. So, we can go
for this thing; this will be this side for instance this is A and this is B. Then A will
be a vertex cover, but is it minimum that is a question. So, can we do in with less
than m vertices? So, it look it is not possible, because suppose we can do. And then so, if
we do with less than m vertices; definitely there are a vertex here, say x which is not
part of the vertex cover, x is not part of the vertex cover.
Similarly, they should be a vertex here y, which is which is not part of the, because
this is more than n is more than m. So, we have taken less than m vertices. So, the should
be a y. So, and also because it is a complete bipartite Graph, there is an edge between
these two - this edge. Who's going to cover them. So, edge between. So, x y they should
be an edge between them, whose going to cover that edge. So, it is not possible to cover
all the edges of this complete Bipartite Graph K m n with less than m vertices.
Next, so, what about the cycle on n vertices. So, suppose if we consider the cycle on n
vertices, what should be the cardinality of a minimum vertex cover. So, here I have drawn
a cycle on 7 vertices. So, let us let us make it 8, let us make it 8 sets cycle on eight
vertices. So now, you can easily see that. So, vertex cover... So, I am marking vertex
cover here. So 1, 2, 3, 4 this is a vertex cover; 4 vertices is enough to cover all the
edges, if we take any edge one of the end point is a red.
Now, the question... So, for instance if this is a cycle on n vertices C n with n even,
then it is clear that n by 2 vertices will be enough we can take alternate one here,
then next here, then next here like that. So, n by 2 will be enough. But then the question
is it possible to do with less than n by 2 vertices. So, without much difficult we can
see that it is not possible, because if we look at each vertex, each red vertex here;
it is only covering two vertices, because the degree of this Graph, degree means the
number of edges incident on the vertex is called the degree. Degree of this Graph is.
So, degree of these vertices only 2, so degree of these vertices only 2.
So therefore, so each vertex is covering only taking care of only two edges. So, together
n by 2 vertices can take care of only n edges. So, for instance if we if we could do with
n by 2 minus 1 that will take care of only n by 2 minus 2 edges. So, the remaining 2
edges will be left and covered. So therefore, n by 2 is a must. Similarly, if we consider
suppose if n is an odd number, then if you can easily see that you will need n by 2 seal
right, because if we have n by 2 say floor also. So, each vertex will cover only 2. So,
that will be less than m.
That that will give that introduces this notion of vertex cover. Now, let us consider another
parameter, it is called we have already talked about independent set. So, the independent
set means, if it is a subset of vertices such that if you take the induced Sub Graph on
this set of vertices, then what we do not see any edges in it. It is it is it is a without
any edges, then it is an independent set. So, given a Graph G, we can ask what is a
biggest independent set in it. What is a biggest cardinality - maximum cardinality of any independent
set in it. So, that number the biggest cardinality if an independent set in a Graph is a called
the independents number or stability number of G. And this famous parameter is the notation
for these things is alpha of G.
We can sorry we can again consider in our. So, for a for getting familiar with this parameter,
we can consider this question for instance in a complete Graph K n, what is the cardinality
of the biggest independent set. So, of case that there is x is an independent set of cardinality
one, because if we just take one vertex, there is no edge on it. But it is possible to have
anything more anything bigger, suppose I take any two vertices in a complete Graph between
these two vertices there is an edge; therefore, it is not possible to have any on independent
set of cardinality more than one. The therefore, the the independent stability
number of K n is equal to one. So now, what about say the complete Bipartite Graph on
K m n, s i s v mention this one right. So, when we have the all these edges m vertices
here, and n vertices; the the biggest independent set. So, it has to be n right; the here you
can see an independent set, n is the bigger number. So, what if what if it is say, because
it cannot be more than that, because suppose an independent set cannot have a vertex x
from here and a y from here, because there is a connection between them. Then edge between
them. So, it is not possible to have one vertex from this side, and one vertex from; either
we have to take all of these things or we have to take all of these things right. So,
the best thing is to take the bigger side.
So therefore, for K m n it will be right, independent this thing is n, because n is
the bigger number. Now, of case we can like this, we can also ask what is the biggest
independent set in a cycle C n. So, n is even when n is even, of case we can take 1, 10
we can take two like that all vertices skipping alternate things. So, we will get n by 2.
So, when it is odd for instance we can consider this 3 vertex Graph, and then here we can
see that this is one. So, then we can now take this or this. So, 3 by 2 floor is the
answer this one. So, you can take a bigger bigger one. So, a 5 vertex Graph. So, we can
take 1 here, 2 here that is it; because if we if we take three here this adjacent to
2, if we take this one, this adjustment to one. So, this is 5 by 2 floors 2. So, so for
an old cycle, it is n by two floor. Now, we are we have study to parameters now;
the vertex cover - minimum cardinality of the vertex cover and the independent set.
The maximum cardinality of the independent set; the next question is is there any relation
between these two parameters, two see this thing.
So, we can. So that suppose, if you remove a maximum a sorry, vertex cover - any vertex
cover from the Graph what will happen. So, if you remove the set of vertices that form
a vertex cover from the Graph what will happen. The remaining vertices that you see is going
to be an independent set; why is it so, because if there is any edge in this in the remaining
collection of vertices, then this edge will not be covered by anybody, because what we
removed was a vertex cover. So, the one of the end point of this edge has to be in that.
So, if you remove a vertex cover from the Graph what we are left with this an independent
set. So therefore, we can see that, if I remove a minimum vertex cover, then what remains
- the n minus the cardinality of the minimum vertex cover, number of vertices form an independent
set. So, that is what we have written here. So therefore, our maximum independent set
cardinality has to be even greater than this. So, alpha is greater than equal to n minus
MVC of G, that is what.
So, so here for instance it was like this. So, suppose this is I draw a Graph like this
now, suppose you you can mark some vertices; as this is the minimum vertex cover here,
let us MVC. So, here we have n minus cardinality of MVC number of vertices. This is going to
be an independent set, this is independent set. So, the biggest independent set has to
be even bigger than this possibly even bigger than this, that is why we say alpha of G has
to be greater than or equal to n minus MVC.
Similarly, what will happen if I remove an independent, suppose this Graph and I I mark
an independent, suppose this is an independent set. Now, let us take the biggest independent
set, independent set maximum and remove it. So, clearly what remains here is going to
be a VC - vertex cover why because any edge is going to be like this only, it is not possible
to have an edge like this. So, any edge is a has at least one of these end points in
this part. So, it is a vertex cover. So, the minimum vertex cover has to be even
smaller than this. So, we get cardinality of the minimum vertex cover is less than equal
to the number of vertices minus alpha of G. This is this cardinality is alpha of G, because
it is the cardinality of the maximum independent set. So, from the earlier slide we see, this
can be rearranged to right cardinality of MVC is greater than or equal to n minus alpha
of G; here in the other side, we can see that cardinality is less than equal to n minus
MVC.
So, together what we get is cardinality of MVC of G is equal to n minus alpha of G. So,
in other words, what we are trying to tell is. So, if you remove a minimum vertex cover
what remains is a maximum independent set. Similarly, if we remove a maximum independent
set; what remains is minimum vertex cover. So, this cardinality of the minimum vertex
cover, we can probably denote by say beta of G, because so we are using alpha of G for
the independent set, and we can use say for the minimum vertex cover a cardinality beta
of G. So, then what we get is the cardinality of this, the cardinality of this, the independent
set - maximum independent set and minimum vertex cover together is the total number
of vertices alpha of G plus beta of G is equal to n - here n is number of vertices.
So, in this class. So, to summarize we have introduce some basic terms that I used in
Graph theory. So, of case there are many more terms that we have to introduce, but as the
class lectures go on we will talk about more and more things. But I would request the listener
to also go through some introductory chapter from any of these books I mention. So, and
solve some problems. So, that he can think a long the class and understand things faster,
and also it is more it is very boring to introduce every small definition in the class.
So, that we can use the forty lectures available for more serious discussion, and then after
that we introduce the few notions like a vertex cover, then we told the minimum vertex cover
is the one with the minimum number of vertices in it. And another notion independent set;
the we talk to about the cardinality of the maximum independence set that is called the
stability number, the notation is alpha of G. And then we related these two parameters
alpha of G, and the cardinality of the minimum vertex cover we called it beta of G is show
that when you some then together we get the total number of vertices. This is, because
when you remove a vertex cover what we see is an independence set.
Similarly, therefore, when we remove a minimum vertex cover what we see is a maximum independence
set and vice versa; that is a reason for that. So, this summarizes the lecture today. In
the next class, we will look at matchings and then we will connect the matchings - the
notion of matchings with the vertex cover, and independent set etcetera. That will be
the aim of the next class. It would be better if the student can as I mentioned go through
some of the introductory material, in many of these text books; so, that the next class
will be much easier.