Tip:
Highlight text to annotate it
X
Welcome to the 18th lecture of graph theory. In this class we will continue with the proof
of Kuratowsky’s theorem. The theorem says the following assertions are equivalent for
graph G. G is planer, G contains neither K 5 nor K 3 3 as a topological minor, G contains
neither K 3 3 or K 5 as a minor. The… in other words, if G is planer graph it is clear
that you cannot have K 3 3 or K 5 as a minor in it. Definitely it cannot have K 3 3 or
K 5 as a topological minor. This is a base because in that, because a planar graph cannot
have non planar minors or topological minors in it. K 5 and K 3 3 really non, definitely
non planar. Now the more difficult part to proof is that if a graph does not have a K
5 or K 3 3 minor then it is planar graph. In other words any non planar graph should
have one of these minors, either K 5 or K 3 3 minors. As you are seen in the last class
it is equivalent to saying that any non planar graph will have either a topological minor
of a K 3 3 or K 5 because if a we have a K 3 3 or K 5 minor then definitely we have the
corresponding topological some of the topological either a K 3 3 or K 5 topological minor also
if K 3 3 comes as a minor then K 3 3 will be there as a topological minor also on the
other hand if K 5 comes as a minor you may get either a K 5 topological minor or K 3
3 topological minor therefore, it is enough to show that any graph without K 5 or K 3
3 topological minor will be non planar sorry will be planar. So, the but, we will prove
it for 3 connected graph first; that means, if G is a 3 connected graph and it does not
contain K 5 or K 3 3 is a minor in it then ah
It is planar this is what will proof then we will we can extend into 2 connected or
even other cases the connectivity less than 3 cases will be easier then now how do we
do this thing. So, we this is the theorem we want to prove let G be a 3 connected graph
and it does not have K 5 or K 3 3 is a minor then we want to show that it is planar. So,
we will just show a planar drawing of it this is our plan. So, we will use induction let
say that for all graphs with smaller number of vertices it is true. So, with a number
of vertices K four also four or less it is very trivial because if K four of case it
is the first 3 connected graph we can start with and a K 5 or K 3 3 minor is not there
in K four now it is a planar graph it is it has a planar drawing therefore, it is a true
now by induction let us assume that for smaller number of vertices this statement is true
and now we need to consider graphs with n vertices a number of vertices in and a 3 connected
and without K 5 or K 3 3 minor
Now, the the point is because it is 3 connected graph there is one edge in the graph such
that if you contract that edge the resulting graph is still 3 connected this theorem we
had studied in the when we studied connectivity. So, this is theorem by and a we can use this
theorem here how do we use it. So, we pickup this edge we know that such an edges exist.
So, x y lets x y and. So, such an edge if i identify and then contract that edge right.
So, this such an edges there x y the point is if you contract it. So, we will get a new
graph. So, with that contracted it will be v x y you know after contracting what will
happen is. So, the neighbors of x and y together will be the neighbors of v x y right the neighbors
of x and y now we can definitely being this is a smaller number of vertices here
The number of vertices smaller here and it is 3 connected and of case K 5 or K 3 3 minor
cannot appear after contraction because after contraction the graph the resulting graph
has if the resulting graph has K 5 or K 3 3 minor then the original also will have;
obviously, because. So, because contraction is one of the operations defining the minors
right therefore, we can see that this resulting graph also defining K 5 or K 3 3 minor. So,
induction can be applied on that by induction assumption we know that it has a planar drawing
and in particular the drawing somewhere this v x y will come right v x y will come and
you see suppose see the v x y some the edges on v x y will go out of it and where will
it go. So, the point is suppose if i had removed this vertex v x y from the graph
It is because we have a 3 connected graph here after removal of v x y we still will
have a 2 connected graph and. So, this in a 2 connected graph they any planar plain
drawing the each face has its boundaries cycle right. So, simple cycle will come. So, it
is therefore, we know that the face in which this particular point is contained that also
will be suppose this’s the face of that. So, that will also be a cycle you know so
So, if you remove this vertex v i suppose i can i can i will i will remove this vertex
v i. So, this is what will see v x y this is what i will see right now we we see that
this edges are going somehow to these some points on the boundaries right that only way
can go v x y now suppose i had removed. So, v x y removed remember v x y as formed by
contracting x and y. So, essentially these neighbors some of them are from x some of
them are from y. So, see them might have come mixed up but, let say first we consider the
neighbors of x along right
So; that means, some neighbors may be disappear may be suppose this disappears this disappears
right. So, we we only return the neighbors of x right suppose these are the neighbors
of x. So, i can draw like this i can draw like this. So, this is now instead the points
where v x y i just put x and then some other neighbors the the neighbors of x which are
not neighbors of y are drawn right. Now, the point is look at the y neighbors
the neighbors of y sorry neighbors of x all the neighbors of x are drawn now i can look
at the neighbors of y how can they come. So, suppose. So, there is a region here. So, this
this essentially they have several regions on the boundary of this face. So, which is
essentially given by the positions of the neighbors of x right one one region another
region right another region right another region another region is it possible that
we have some y here inside suppose is it possible that v of x i mean each of the regions other
then is a not touching not including the the neighbors of x itself is it possible that
no y appears in the interior regions anywhere So; that means, the y are always on the on
the positions where x neighbors are placed right the same same vertices right; that means,
essentially y will share the neighbors of x but, then at least 3 neighbors should be
they y should have at least 3 neighbors right So, i should have at least 3 neighbors so,
it will. So, happen that. So, we can right. So, it y y can be like this. So, it can be
some 3 neighbors it can be now what do we see if y has 3 neighbors shared shared neighbors
with x. So, see not need not be this consecutive you can explain all the neighbors also here.
So, suppose this neighbor of x and this neighbor of x and this neighbor of x is shared by y
right and see y x also has. So, then you can see that the 3 neighbors
together will form. So, these 3 neighbors together will from one. So, that say i can
i can draw it black. So, this one to. So, because of the 3 neighbors which which has.
So, one 2 3 these the triangle here that these 3 neighbors and then this is connected to
this this and this and x is also connected to this this and this and between x we have.
So, essentially we have a connection. So, essentially we have a K 5 available here right.
So, moon more nearly we can draw here
So, it will be for this is the x 3 neighbors now between them. So, we see the triangle
one 2 3 then the y may be here y and y is also having these 3 neighbors. So, together
we have a K 5 here. So, this triangle this this this and this and this together we have
a K 5 minor here. So, it is a contradiction to the assumption that there is no K 5 minor
in the graph. So, see of case you can assume that the when i selected between x and y.
So, i decided that x as smaller neighbors than y. So, suppose y has only 2 neighbors
right. So, i has only 2 neighbors. So, then it will. So, happen that x also will have
2 neighbors maximum and these 2 neighbors if i remove this 2 2 neighbors right see because
x should have. So, this is x y at least 3 edges should be going out of x and y.
So, because a 3 connected. So, if there the only 2 neighbors for x then y also y then
x also only 2 neighbors and then together this removal of this 2 vertices will disconnect
this portion from the rest to the graph therefore, it want be 3 connected right. So, that is
why we are see saying that they at least 3 neighbors of y and if they all are shared
with x then we already got a K 5 minor right now it means that they should be some lets
again again draw this thing x in this interior the region of this thing which a way which
a mark here this region this region and this region which is not including the in the neighbors
themselves the portion of the neighbors themselves they should be at least one say this here
at least the y has i am drawing y is y here. So, i have at least one neighbor here right
now where else can y’s neighbor b. So, and claiming that all the neighbors of y has to
be in this region there in the same region in the same segment here right. So, y suppose
including this we can have we can share this neighbors of x but, it cannot go beyond this
thing suppose it goes beyond this thing suppose say y has a neighbor here right somewhere
else. So, then what happens is. So, you see this connection is there. So, these 2 are
there now you can see that here we have already got a K four K 2 2 right K 2 2 including this
vertex this vertex and this vertex and this vertex already defines a K 2 2 like this minor
K 2 2 minor here right and then how here is a the third we can add make a K 3 3 by adding
this and this on different sides of the K 2 2 right because this on the a side this
is on the b side right and these 2 neighbors can be on the a side and these 2 neighbors
on b side right So, this will make a this this this these
3 vertices and then this this and this will be the other 3 vertices. So, this will be
x this will be y and these are the 2 neighbors of x and these are the 2 neighbors of y we
have this connection right and we have this this also here because that is what this circle
the circle provides that connection. So, here to here one edge here to here one edge here
to here one edge here to here another edge K four sorry K 2 2 right that K 2 2 and together
with this thing will give a K 3 3 minor K 3 3 minor right
So, this is these tells us that. So, maybe we can draw it a little more clearly. So,
i am showing you the K 3 3 minor in case. So, the. So, this as x neighbors this is x
x neighbors here suppose in between here. So, y as a neighbor and then suppose y has
a neighbor beyond in not in this region if suppose beyond this region then what happens
is y i take y. So, this sorry i can i can color it yellow as these 2 and this this is
y. So, these 3 as one side and then x sorry these are use orange color this this and this
and other side in here we have the connections. So, here here is a connections sorry is a
connection here is the 3 connection to the yellow vertex and then this yellow thing this
is there is a connection there is a connection like this here in there is a connection here
and then there is a connection here see
This is. So, that is the every vertices connected to every brown vertices connected now to every
brown vertices connected now to every yellow vertex to be brown vertices connected now
to every yellow vertex and every yellow vertices connected to this is a K 3 3 is a K 3 3 right.
So, what we infer now is that all the neighbors of suppose these is the thing
So, if you for consider x and this this the portion of x and all the neighbors of y should
be in this region only. So, it is may have some other things here. So, the all the neighbors
including this points through y y neighbors all will come here. So, which means that i
can place y somewhere here and then i can necessary i can connect in like this and then.
So, this will be a planar drawing of the original graph see the key point is we can argue out
that y comes in one of this sectors right So, inside. So, it will not go in there one
be any confusion about how we can place y with respect to the the the graph which contains
only x after removal y right we can nicely place it in segments and all the neighbors
are y will be inside this region only So, that is y we can we can get a drawing
of the graph from the smaller drawing. So, it it follows that. So, if there are 2 2 things
you have made use of one is there is no K 3 3 minor in the graph then one is a K 5 the
graph is K 5 minor free another is 3 connectivity if all these conditions for met then we can
we have a argued that we can get a planar drawing of the graph; that means, the graph
is planar right
So, the using induction now the the only thing left is to show that suppose it is not 3 connected.
So, the connectivity’s only 2 or one or something like that then also we can get a
planar drawing provided K 5 or K 3 3 minors not there. So, what we can do is suppose the
connectivity’s 2 so; that means, there as 2 there are 2 vertices right. So, when you
remove these 2 vertices they will get disconnected into 2 pieces. So, we can see that. So, there
are 2 possibilities. So, then here there is an edge or there is no edge. So, whatever
it is we can we can assume that there is this edge
We will if it is not there will put it right and then we consider this graph this is g
one and then this is g 2 see by putting this edge see see to see that K 5 or K 3 3 minor
will not be introduce if it is was not there before edge will leave to the to verify that.
So, the the the why why is it. So, because again suppose the minor is intuitively this
is the reason suppose the minor is such a minor is introduced. So, you can you can see
that this edge right because is it 2 connected graph even if the edge is not there right
the the minor the the minor which got introduced here has to be totally from g one totally
from g 2 it is not possible that the minor shares it is brand vertices from g one and
g 2. So, a little bit of it is here and little bit of here. So, because it has to be totally
from here because of because this K 3 K 3 3 and K 5 or the 3 connected graph the for
instance if there is brand vertex here. So, how can how can suppose how can the share
it between the 2 sides. So, suppose if there is one vertex here right
And. So, all the other brand vertices are on this side right. So, it has 2 of parts
to the other side 3 if there are 3 vertices on this side they should with 3 different
paths from here to here right because of the 3 connectivity and that is not possible because
there is only 2 vertices in the separator we can only 2 have to disjoint parts. So,
we can infer that if K 3 3 or K 5 is a minor of this entire graph the after putting this
edge right then it is it is it is completely from this part or completely from this part
we can see a K 5 or K 3 3 whichever is in g one or g 2 right
And now even if this edges not there we could of contracted suppose it was there K 3 3 minor
K minor in this thing it say that that this edges critical for that but, then this edge
can be produced by contracting this entire portion because there is at least 2 edges
here and they should be because of the connectivity of this they should be some path and then
this will become an edge here right when you contract this entire region into here right.
So, therefore, , it will it will. So, happen that so, the we can we can we can produce
this K 3 3 minor in the the in the total graph also right
So, in other words if you consider a the connectivity as 2 or for that matter even one even in this
case it is like that the argument is correct right. So, the assumption that the entire
graph does not contain k 3 3 or k 5 as a minor in it means that. So, this portion alone or
this portion alone also does not contain K 3 3 also K 5 minor similarly, if it was the
connectivity was 2 is this was the picture then this portion this portion even with an
addition of this edge cannot contain K 3 3 or K 5 as a minor because if that minor is
there in one of them it should have existed in the bigger graph also that is the reason
So, then we can see that this smaller portions can be drawn because they are 3 connected
and or by induction make and say. So, the smaller pieces can be drawn on the plain and
then we we we have to do some scaling and adjusting. So, what what we do is we can draw
one of them and identify the edge and make sure that the face is right they consider
the face in which that edge is appearing and then we have to make the other parts smaller
and bring that edge on the outer face and then draw it
So, i leave it to the student to verify this details but, it is not very difficult. So,
or other rigorous statement is available in details book you can read from there we will
skip that portion to avoid it tedious details. So, the that point is just imagine to plain
drawings for g one and g 2 and think how we can draw a plain drawing for the the complete
graph by pasting them together on the correct place because there is that an edge one edge
and that and not that the face containing that edge can be made the outer face and we
can bring that particular edge in the correct place in after making its smaller the picture
making its smaller and then we can paste it in the correct place and get planar drawing
that be i leave it to the student if figure out the technical details of that. So, the
multiple the more interesting portion was the to provide for 3 connected case right
So, now with this thing we will finish the the planar portion we will revisit planar
it a little latter but, today my intension is to do different kind of coloring and different
kind of coloring called list coloring this is also an important topic in the. So, this
is a way we are defining the list coloring. So, we are given a graph and along with the
graph for each vertices of the each vertex of the graph we are given a set of colours
also; that means, essentially to each vertex we are associating a list our condition is
that the vertex should be coloured from using one of the colours from that list on the other
words the vertex does not allow any other colour any outside colour. So, it has a list
of colours and it is interesting that it will get coloured by only one of the colours from
that list. So, the a coloring such that each vertex gets a colour from the list associated
with it is called a coloring of the graph from the list you from the list then we will
say that a graph g is K list colourable or K choosable.
If our every family. So, as we. So, with the cardinality of the list is equal to K then
there is a proper vertex coloring of g from the list see the point here is the the list
can be anything but, the only thing we know there is each vertex has a list and it has
at least K colours in it the the content of the list may be anything but, just the length
of the list are how many colours are there then the list is known K. So, but, then they
should be able to say that you respect you to whatever in the list as long as the list
sizes the cardinality of list are at least K we can come up with a coloring for each
vertex such that the colour is from the list for each vertex and the it is a proper colour
and it is a proper coloring in that case we say that the graph is K list colourable see
suppose if a graph is K list colorable ah Then you can. So, fine and another another
thing we have we need to understand is. So, suppose this K this smallest value of K for
which this happens is a the follows smallest value of K four which this happens is the
the list coloring number this chromatic number of the graph or choice number of the graph.
So, we also say that the graph is K choosable. So, this the smallest K four which is the
graph the g is K choosable is the list chromatic number of the graph list chromatic number
of the graph them now the. So, of case to understand it for instance you may see you
may say why for instance can i can i suppose can i colour a graph suppose every every every
vertex as the the same list same vertices the list of size one then definitely you cannot
coloring because then the each vertex says that i have to get this color only right for
instance So, if there is an edge. So, but, on the other
hand. So, if a graph is K list colorable if a graph is K list colorable; that means, respective
of the list content of the list just the guarantee that each list has at least K colors in it
tells us that the graph can be colored with the colors from that list then it also clear
that it is a K colorable then usual sense of the coloring why is it. So, because we
can as associate with each vertex the the same list namely one 2 3 up to K and; that
means, that any vertex can any vertex can be colored with any of the colors from one
2 K right So, in that case if a coloring happens; that
means, it is a K K K coloring only we say that K we can get a coloring of the graph
using K colors right. So, because we are not restricting the colours that can be s assignable
to a vertex other than saying that it has to be from one to K right
So, therefore, it is very clear that the choice number of the graph g is always greater than
or equal to chi of g right because if the choice number is some K then some of chi of
g also chi has to be g has to be K or less right. So, but, sometimes choice number can
be much greater than chi of g. So, the next our see the and another thing is for instance
if you see some of the our earlier bounds like the greedy coloring strategy will it
working the case of list coloring also,. So, you can see that suppose you have an ordering
of the vertices in such a way that. So, i write the vertices in the order v one v 2
v 3 and v four v n with the property that v i right has at most K neighbors in say v
one comma v 2 up to v i minus one suppose such a ordering says we have see that in this
case K plus one colours are enough to vertex colour the graph
Why because we will colour v one first and then v 2 first v 2 second and v 3 next and.
So, on when whenever i try to colour v i the only the vertices starting from v one and
ending at v i minus one has got colours and can be look from v i we see that only at most
K neighbors of it are coloured then we can be we can use the K plus one’th available
colour for v i and therefore, it can be coloured using K plus one colours this was the greedy
strategy and then essentially we told K K plus one as the coloring number right
So, for K was the of the graph now thus same K can be an upper bound for the size of the
list so,. So, that we can come up with coloring of the graph right one other words the choice
number or the list chromatic number also can be upper bound by the same K how is it. So,
because now to each vertex we are associating a list of cardinality at least sorry this
K means K plus one i mean the list a list of size K plus one or more and
Now, when i colour starting from v one and then the v 2 and v 3 and one words then i
reach v i we see that the the we see that the the the colours which are already used
on its neighbors right say essentially because v i will see its coloured all its coloured
neighbors are from in the range v one v 2 v 3 up to v i minus one and then we know that
only K neighbors are there only K colours are used up but, it is list as at least K
plus one they should be one more colour available to it in its list
So, it has to take it from takes from its own list earlier we were using just any available
colour now we have to insist that it has to list colour from its own list. So, but, then
because K any list has at least K plus one neighbors then you can always kept one more
colour and therefore, it is possible. So, the same argument works here altherefore,
the general c plus one coloring number still a bound four in particular maximum degree
plus one is a bound right Similarly, brooks theorem can be proved also
for this case without much effort therefore, we we see that some of the bounds which working
for the vertex chromatic number the is also an upper bound for the list chromatic number
Now, the next point is we have to see a case where the the the for instance planar graphs
if you consider it is a four colourable vertex coloring but, then it needs 5 colours for
list colour right. So, its list chromatic number is 5 but, how do we show that the planar
graphs are 5 list colourable how can i show that if with every vertex if i associate a
list of cardinality at least 5 then we can always come up with proper vertex coloring
of the given planar graph from the given lists right
So, have to do this thing so, this is the one extreme. So, this is also a result from
messent. So, will show that this every planar graph is 5 choosable. So, the. So, the that
key points here is to rather than this an induction proof but, rather than doing the
induction directly on the for this statement like means every planar graph is also lets
consider a smaller planar graph in assume that it is 5 choosable then i will try to
extend the 5 list coloring of this planar graphs to every bigger planar graph this not
the strategy rather than doing this thing we will slightly strengthened induction assumption
and then will prove the induction for that stronger statement this a is slightly delicates
strengthening of the induction hypothesis this is that trick here
So, how are we going to do this. So, this is less strengthening. So, know suppose that
every inner face of g is bounded by a triangle and its outer face by a cycle. So, we consider
a plain graph plain drawing and we say that suppose there are several inner faces the
all of the inner faces are just triangles and outer face is bounded by a cycle. So,
v one v 2 v 3 up to v K and v one it maybe a K length cycle suppose further that v one
has already has already been coloured with colour one and v 2 has been coloured with
colour 2 suppose finally, that with every other vertex of c a list of at least 3 colours
is associated and with every vertex of g minus c a list of at least 5 colours is associated
then the coloring of v one and v 2 can be extended to a coloring of g from the given
lists this is what we going to prove. So, on other words. So, you consider as special
planar drawing
So, the requirement is that our outer face this the only non triangular face which are
which were allowing on other interior faces should be see triangles already triangles.
So, and. So, this can be number. So, v one v 2 v 3 v four v 5 v six and. So, on up to
v K this can be number like this the inner faces are triangles the outer face only is
scaling cycle now also we assume that this is coloured this is also coloured these 2
colours are already known to us right now we will say that the lists are there for for
suppose a vertex like this for a vertex like this there are 5 colours 5 colours associated
in choice 5 lists the lists are of cardinality 5 each lists contains 5 colours in it but,
the vertices on the face they contain only say 3 they only 3 3 colours in it they can
be any 3 So, 3 only 3 colours right. So, see it is
possible that this red and green also maybe part of this v one and v 2 are already coloured
this may be part this things but, we do not have a any control at least 3 colours are
there right Now, we say that see we can get a coloring
of this planar graph this kind of planar graph from that lists from the lists each vertex
will get the colour from their only list and we can retain in that coloring even you even
retain the already given colours of v one and v 2 this what the strengthening suppose
this is true this statement is true this is some as this is a stronger statement then
what we need why is it. So, you may say there why it looks like a special planar graph is
not the case because you see if you given a planar graph you can always add edges to
it and they because when you add more edges the number the requirement of colours may
only go up right
So, if after adding few more edges if you can still colour that graph then the earlier
graph can definitely be colours because after removing that edge coloring will not be spoiled.
So, the more edges only create trouble. So, what we do we make the planar graph maximal
by adding as many edges are possible. So, when the planar graph becomes edge maximal;
that means, it is a triangulated planar graph the outer face will become a triangle so,
we can say that here right
So, already 5 colours are there suppose are 5 colours are given to all of them now let
us colour this v one and v 2 with 2 colours say red and green and then you see red green
and then here of case this is the all the conditions of this thing this is triangulated
graph and then all the conditions of that statement is met this outer face this is already
coloured with one thing and this is 5 colours instead of 3 fact all the interior face is
have 5 colours and therefore, interior vertices of 5 colours and interior faces are all triangles
and here the exterior face the outer faces also triangle that is all therefore, definitely
if that statement is true you can extend this coloring v one and v 2’s we has already
got colour then everything can get a colour colour from there corresponding this therefore,
if these statement is proved then whatever statement we are looking for; that means,
a planar graph has 5 choosable is immediate because we just have to consider the maximal
planar graph then is because the outer cycle becomes a triangle in that case that is all
And now we see therefore, we just have to prove this thing. So, essentially we are trying
to prove is stronger statement therefore, right. So, because here we have much more
things because you know that some other vertices only 3 colours in it in their list so,me the
remaining things have 5 colours but, 2 vertices are even precoloured i mean in sense they
already got there coloring therefore, it will it will require some more effort will assume
that it may require some more effort but,. So, happens that this strengthening helps
us to proof it faster because induction hypothesis also in get strengthened right now will let
say this is the thing. So, we will consider this outer cycles
So, outer cycle looks like this. So, this the outer cycle. So, this is v one v 2 v 3
v four v 5 v six and v K right. So, first thing we do is we see that there is any code
for the thing is it possible to find some some code say this is the code right code
means some vertex to direct edge connecting some v i to v j some v i to v j this can be.
So, it is possible to find such an edge right So, see it not necessary that such a code
exist suppose such a code exits; that means, the direct connection direction connection
is not non adjacent vertices on this cycle a connected by a code if such a code exist
then what happens says you can see that here there are there are 2 cycles visible right
one and this definitely is a smaller number the number of vertices in this induce sub
graph will be smaller right here whatever and of case this will be triangle it turned
inside right So,. So, whatever therefore, the all the conditions
required for that statement is met because is the each interior face here is triangulated
and here all these things of 3 colours associate with that this this can you can give some
colours to thing whichever from the list one of the colour without the 3 colours one colour
here and then the another colour taken from and we can get a coloring of this thing by
induction hypothesis Now, once you colour this thing. So, we can
consider this portion. So, this portion this portion means here see this 2 vertices already
got colours because of this coloring other part and nothing a is shared other then these
2 vertices right these 2 vertices vertices Now, all the other conditions like interior
triangle interior faces are triangle and 2 here also right. So, and here if you go through
they also have 3 colours in the list interior face 5 colours only thing is these 2 has already
got colours from the coloring of this part this part. So, therefore, , we can apply the
induction on this thing on this portion and get it see therefore, if there is a code for
the outer cycle then we are easily through the reason is we can that code will help us
to see this outer cycle splitting into different cycles one this here and the other this here
right and for one of this induce sub graph here this cycle and the interior vertices
here of we can apply the induction and get the coloring as we need and then return the
colours for these 2 only common vertices and then extend the coloring to the remaining
part the green cycle here right
And the interior vertices. So, that cases. So, that cases easy. So, if there is a code
then the things becomes easier in this case. So, the therefore, what we are going to do
now is to assume that there is no code; that means,. So, this the this is the cycle the
outer cycle this is v one v 2 v 3. So, this the v K. So, v K minus one and. So, on right
there is no code; that means, nothing like you can you cannot see any code here in particular
if i look at this v K and v K minus one and if you look at the shortest path from v K
minus one to v one it will it will contain more vertices right one or more vertices in
it it form a code direct on be there Now, you see that if it is a shortest path
right and if you look at the neighbors of. So, this is there is a path here if you look
at the neighbors of a v K. So, v K minus one is neighbor one neighbor. So, we get some
neighbors here right it’ll it will look this and then we can see that. So, the because
of this because inner face as at triangles. So, it should right. So, essentially they
should be a edge here. So, now, this along this we should get a path like this right
the neighbors should along the neighbors they should get a path along the neighbors we should
get a path. It is not even possible that there is there
some gap here because i can once i can if i if i if you look at this thing is not possible
to have a vertex of this vertex otherwise because how can it be triangulated face right
it is not possible. So, should be just including this neighbors we should have a path from
v K minus one to v one along with this tuff because that is the all because all the inner
faces are triangulated this faces has to be a triangle and this face has to be a triangle
then the next has to be a triangle then next has to be a triangle and then finally, it
reach here So, this is the structure we get now what
we do it is. So, here see call that by our assumption we have v one and v 2 have colours.
So, this is coloured one and 2 suppose. So, maybe you can used 2 colour for this thing.
So, this is already precoloured and also this maybe its yellow colour is already there violet
colour is already there violet colour is already there now the yah
So, now v one and v 2 already coloured now now what we do is. So, here we will look at
the colour list of colours of this there are 3 colours on that right 3 colours now 3 colour
out of this 3 colours one of them can be one this colour sorry this yellow but, then there
are other 2 colours other than yellow right. So, those 2 colours i will remove from each
of this neighbors each of this neighbors except here here i will retain like this because
here this has only 3 colours v K minus one only 3 colours we cannot get rid of 2 colours
on that because the number colours will go now. So, the v K we will not disturb but,
all these case internal vertices they had a 5 colours then therefore, we can get rid
of 2 colours from that which are the 2 colours because v K had 3 colours on it
So, other than the yellow colour which is already on the v one we will take out the
remaining 2 colours and get rid of all those things there right now what happens is when
i the my plan is to consider this this cycle. So, this and entire cycle this cycle this
is the route a excluding v K right. So, now you see that all these v one and v
2 has already got colours v 3 v four all these thing up to v K minus one had 3 colours we
have in disturbed them and then these case which had before 5 colours have lost 2 colours
on that at most maybe there may not have lost but, then if they had shared some colours
with v K they have loss those 2 colours on that right
Now, let say those 2 colours which were removed our red and say green red and green colour
were remove from the list. So, they also have because initially they are 5 colours now 3
colours are now you know that by the induction this can be coloured because all these are
interior interior faces are triangles and all such such assumption has still true here
for this thing and these 2 are precoloured and every every outer face as a 3 colours
interior faces 5 colours therefore, it can be because the number of vertices as reduce
by one it can be coloured a from the lists right
Now, what we do is you look at the colour by that coloring which colour came for v K
minus one see if it is not red or green we can use red or green to colour this thing
for the red and green is not anywhere in the neighborhood in this is already coloured one
and then this is different from red or green and therefore, this will be valid coloring
because if i give red but, in case red or green came suppose green came here then give
red to this if red came here then give green to that.
So, it means that we can extend the coloring of v one and v 2 to the entire graph in the
previous case when the code is there we remember that the v one and v 2 were precoloured. So,
that; that means, this and this is already got colours therefore, we start that we start
from this side because we have to extend that first and get colours of this thing and then
extend another side. So, i had forgot and tell
So, therefore, this is the way we prove that planar graphs are 5 choosable and then it
also see this also gives a different proof for a the fact that minor graphs are 5 colourable
because it the earlier proof for used euler formula and then the the typical the the Kempechi
argument we had used. So, the we have use a small different strategy of considering
the parts form by 2 different colours and some. So, but, in the last class we had done
that but, here is a proof is does not involve any of those things is just induction proof
but, here the stealthy in the induction hypothesis and the strengthening the clever strengthening
of the induction hypothesis right this is. So, with this we will finish this class and
in the next class will consider the list coloring for edges say edge which chromatic index will
consider the edge coloring version of the list chromatic number thank you