Tip:
Highlight text to annotate it
X
Welcome to the seventeenth lecture of graph theory. So, in the last class, we were discussing
about planar graphs. So, the main thing that we proved in the last class was that for any
connected planar, so the number of edges 3 n minus 6 number of edges were at most 3 n
minus 6.
Now, using this bound for the number of edges, we can show that the planar graphs can be
six colored. This is what any planar graph can be vertex colored using six colors. So,
how do we do this thing? So, the first thing there is, we need two observations. One is,
if you take any planar graph and any of its sub graph, induced sub graph or sub graphs,
it will again be planar graph .Why is it so? Because, if this graph can be drawn on the
plane, without the edges crossing each other, then definitely any sub graph of it also can
be. We just have to delete the the vertices or edges which are not part of a selection
right. So therefore, that is one point. The second
thing is that, because the number of edges at most is 3 n minus 6 n 6 sum of degrees.
If you add up degrees or the vertices is at most how much 6 n minus 12. That is because
each edge contributes two each to the sum. So, if there are only 3 n minus 6 edges, the
maximum of 6 n minus 12 can come from such a sum.
And now, if that is a situation, we know that there exists a vertex, say x of degree at
most 5. Why is it so? Because, if this is the sum of degrees and if all degrees were
6 or more, then the total will be at least 6 n right, 6 n which is greater than 6 n minus
12. So, they should be at least 1 vertex whose degree is at most 5. This is the main thing.
So in that case, what we can do is an inductive coloring namely, or in other words, what we
can do is to arrange the vertices in an order. Say, we can arrange the vertices in an order
this way. So, let say x 1, x 2, and x 3. So this x n be the vertices. So x 1 is the vertex
of degree 5. So if you look at neighbors of x 1, there are only at most five neighbors
to this side right among these things. Now if you look at x, the graph on x 2 to
x n that is again a planar graph. We have, we will select x 2 in such a way that that
is a vertex of degree at most 5. We know that any planar graph has a vertex of degree at
most 5. In particular, this induced planar graph on x 2 x 3 up to x n also has 1 and
then, without loss of the generality, let us name that vertex with degree at most 5
to x 2. So it means that, the number of neighbors
of x 2 in this collection is about, may be possible that there can be connection backward
but, that does not count. We just count its neighbors, the forward going neighbors. Then
similarly, x 3 is that vertex whose minimum degree is at most 5 degree in this induced
graph of x 3 to x n. So, there is at most five neighbors in this connection, at most
five neighbors in this connection. So such that, so the ordering is such that, if you
take x i, so its number of neighbors in x i plus 1 x i plus 2 up to x n is at most 5.
And then, we start coloring from x n onwards. We first color x n with an arbitrary color.
This will be colored first and then x n minus 1 will be selected so that will be given.
So, when up to x i plus 1 to x n, we have colored using at most five colors, at most
five colors right. Sorry at most six colors right, let us say. Now I consider x i. We
know that in this collection it has only five neighbors at most. Then therefore, how many
colors are used up already? Only five colors I used maximum because this can take, these
all can take different colors and total of five colors may be used up.
Now this can use the 6th color available right, 6th color available. So like that, we can
go all the way up to x 1 and then once x 1 is also colored using at most six colors,
so the inner graph is six colored. The key idea here is not new because, we have already
discussed this kind of coloring when we studied the greedy algorithm. There, we were just
saying that any vertex we will have at most delta neighbors. Therefore, delta plus 1colors
have enough but, here we have a special ordering in such a way that any vertex is only is adjacent
to at most five neighbors in the higher in the in the list of higher number of vertices
right. So, that is why, we can color it with six colors.
So, this is simplest color and the and simplest procedure to color the planar graph that is
using six colors. Now, we will show how this can be improved. In fact, it is possible to
show that if any can be planar graph can be colored using at most five colors. How will
you do that? So, again an inductive strategy. We will have to order the vertices in the
the the in such a way that, if I take a x i, the number of vertices which are adjacent
to it from the list x i plus onwards to x n should be at most 5. The same list thing,
so we will inductively colored. So, first x n will be colored, x n plus 1 be colored.
This time we are making sure that we only use 5 colors. Say up to x i plus 1, we managed
using five colors.
Now to deal with the x i with x i, we will see how it happens. So x i, as we have discussed,
it has only five neighbors at most right. It can be less, so five neighbors at most.
Now by induction, we know that we have already colored the vertices starting from x i plus
1 to x n. So, all these vertices, can they assume to have some color right. We can we
can assume that these are all colored already right.
So, if x i has less than five neighbors, then we will see only four or less colors. So,
we will we can use the 5th color for x i. So, will assume that there are five neighbors
and what if there is a repetition of colors on the set of neighbors. For instance, the
yellow is repeated twice which means that only yellow, red, green and violet is used.
So, only four colors are used. The 5th color will be available for, so I can use the 5th
color to color x x i. So, so we can assume that all the five available
colors are present on the neighbors of x i. That means there is no repetition of colors.
So, maybe you can select another color, black color say. So, this is so these are all black,
yellow, violet, green and red. So, all are differently colored. Then how do will I manage
to get a color here without conflict right.
So, this is what you are going to discuss now. So, we can assume that so this is this
x i. So, around we can assume that we have this is a common point x i. And then some
distance, we consider it can be a very small distance. We can, I think that these are some
epsilon distance. Therefore, you can assume that this is straight lines here. Now, so
we can consider this black green vertices right. So, when consider the black and green
vertices, so we can consider as we did earlier. We can consider the path, so we can consider
the path right. We consider the path starting from black to green. So intuitively, you can
see that if you start from black to green, so it will, it can either go like this and
reach here or it can either go like this and reach here. In whichever case, this path right,
if you if you trace out that path, any path you can trace out, any path, so the path will
have to separate this red vertex from this. For this vertex right, is it not? So, that
is the key point. So, it has to separate so it can be like this. So, it can be you can
see this will this will complete a close region and then this will be inside, this will be
outside or it can be like right. For instance, you can you can think that path can be the
other way. So how can it be?
So it can be here. I can go like this and come here but, in that case also the red will
comes inside this closed region and this will be outside. Somehow, this will separate, this
region containing red vertex from the yellow or violet vertex right.
Now the question is, can I have a path starting from, it is ok fine. So, this is true about
any path. Now the point is to consider a black green; the only black green vertices in the
graph, black and green vertices on the graph and so you see with several connected components
of black and green vertices will come, if you consider only the black and green vertices.
Now the question is, in which connected component this green vertex and this black vertex. That
means, that this black vertex and this green vertex the neighbors of this this thing will
appear. Is it possible that they belong to two different connected components, right.
If suppose, this black component belongs to connected components, so also black green
using right, so it is possible, is it possible that it is it belongs to different connected
components. Is it possible to belong to different connected components, right.
It does not belong to different connected components. It is because, if it belongs to
different connected components, suppose this connected component of black and green is
different from this alright. If this is so, what we can do is here, we can exchange the
colors green and black. So what what you mean is, all the black vertices here will be become
green. That that means, these vertices will become green and the green vertices will become
black that means, these vertices will become black right.
So, here in particular, yeah, this will become, this will become green right. So, then what
happened is there are two greens on the neighborhood. So, there is a repetition of green color for
this thing, as we discussed earlier. So the existing is green, yellow, violet and red
only. No black, so black can be given x right. x can be colored with black black color now.
So, this is what will happen.
So, what we can infer is that if you consider the green and black components of the form
by the green and black vertices, so the the component in which the green neighbor is contained
will be the same as the component in which this thing is contained. So in other words,
it is it is it is that here, there will be a connection between these two components.
This and this, somehow it will it will come all the way here and collect, so there will
be some, so there will be some red black connection all the way from here to here. So, not red
black, the green black color connection from other.
So if this is a connected graph, then you can also see a red through the connected component
containing this vertex and this vertex. We can also see a path right. We can also see
a path of red and black vertices starting from this black neighbor of this x and reaching
the green neighbor of x. So it will be like this. So, we have the the new vertex and here
we have its five neighbors. So, we have selected the black vertex and we have selected the
green vertex. Let say our path is like this; green black, green black, green black, green
black, green, sorry, this is green, like this somehow. As we have already discussed, that
will separate this red vertex and say yellow vertex from each other.
So now, you can see that if you if you consider now the yellow and red irelends, yellow and
red connected components, so again, we can argue that the yellow and red connected components
should come in like this. When you consider the yellow and red connected component, this
vertex, this yellow neighbor and the red neighbor they should belong to the same connected component
like as exactly as we are argued for black and green. So, they should because, otherwise
one of the connected component in one of the connected components involving red and yellow
vertices, we can exchange the colors yellow and red and then that will cause a repetition
of colors in neighborhood of x, which means that color is released, one color is released
right. So it it so happens that it we cannot do that.
Because, we have to assume that it cannot be color right. If you can colored then. So,
it should happen that the, even you consider the red and yellow components, connected components,
the same connected components should contain both these neighbors of yellow and red neighbors
of or vertex may, the central vertex, this new vertex.
So, it should so happen that, so there should be a red yellow path starting from this yellow
neighbor to here. But, how will it reach? It has to somehow cross this boundary. We
have drawn with green and black vertices. So, it cannot cross it through any edge right
because, if it crosses through an edge that means the edges crossing. Because it is a
planar graph, we cannot do that. So, this will come and this this is not possible; so
otherwise it is not a planar graph. So, it should probably cross through one of
the it should hit a vertex and get into this. But then, hitting a vertex and getting this
will away common vertex. This this particular vertex will be common vertex for this green
or black, green black path and the red yellow, red yellow path and which should be the color
of this one yellow or red or green or black. It is not possible because if I say yellow,
then this this path will say no, no. This path allows only green and black but, if you
say black was something, so then, we will get a contradiction because in other part,
it should be a path, should be a red or yellow vertex. So that is not possible; so it is
not possible for it to come. So, what we assume is what we get now is that
the connected, the same connected component cannot contain both these yellow neighbor
and red neighbor, which means that there is this color switching strategy for one of them.
So the red, one of the components can switch color red to green. So, it is red to yellow,
which is essentially means that it will produce a repetition of colors there and then that
will allow us to color. Use the other color, the 5th color for the central vertex. This
is the idea. This is the idea of coloring. So the next question is, will be is it optimum?
So is it that, is there a planar graph which requires five colors to vertex color it. The
answer is no. In fact, planar graph can be colored using four colors. This was one of
the most important questions in the history of graph theory. So whether a planar graph,
how do we color a planar graph with four colors? So is it possible to color every planar graph
with four colors? We have already talked about the map coloring problem so. So, this some
several people attempted this and then finally, came with a proof using the help of computers.
Finally, the proof is not so elegant in the sense that it requires computers for very
fine finally some other cases. So then, but again this this is solved after a century
of struggle. So but, the proof is so long that we cannot discuss the proof of four color
theorem in this lecture. So, we will be happy with just the proof of five color theorem
right. Now, so, we have explained already, explained
how planar graph can be four colored. So, our next intention is to go ahead with one
more important theorem in planar. Even though it is not very related with the coloring,
so we because, we have started with planar graph, so we will just getting to this important
theorem, a characterization of a planar graph by kuratowsky. So this this is our next team
and of case, so we will we will not give all the details because it will some of the details
will take time therefore, we will we will just leave the simpler details. We will leave
it for the student work out himself so but, main ideas we will cover.
So, we have to, when I want to explain this result, I want to remind the student about
some of the concepts we had earlier discussed. So, this is the one concepts was that have
minus. So, this was like, when when do you say that a graph is a minor of another graph.
So if you say, h is a minor of g, if you remember, it was when h can be got from g, by repeatedly
applying three of the following operations. One is deleting a vertex, the second is delete
an edge, third is contract an edge. We are familiar with these operations now. So, that
is when we say that h is a minor of g and second thing was that, yeah correct.
So, you will you will develop, so you will say that suppose deletion of deletion of vertices
and deletion of edges let us forget. Suppose from g, if h can be obtained by a series of
contractions, then we will say g equal to m h, so h is minor of g but, from, so that
means somehow g can be obtained from h by some reverse contractions, is what we mean.
So it is not be very clear. So, what we intend to say is that you start from g and if you
apply a series of edge contractions and if you can get h, then we will say that g equal
m h. This is the notation we want. Then similarly, so the the other concept we had when related
related to minus was that of. For instance, if g equal to m h, then we can see g vertices
of g is partitioned in to a collection of vertices v 1 v 2 v 3 up to all the way up
to v say cardinality of h. That means, so the corresponding to each vertex of h, I can
get a collection of vertices of g right. This is the brand set corresponding to the vertex
set of h right. Then so, we see that, whenever, so this correspond to the vertex of the u
1 u 2. We can see, sorry, this is u h right, u 1 u 2 u 3. So u 1 u 2 u 3 may be the, may
correspond to vertices of h. Whenever there is an edge between u i and
u j edge, we have we have should get at least one edge between this collection which is
a vertex set of, which is subset of vertex set of g and between these collections right.
So that, it should at least become more than one edges but, it should be 1. So, we should
get pattern like this. So this this for instance, if you if you consider this is one vertex
and if you remove the multiple edges coming across this, then it will it should happen
that we get back h. And more over there should be; this should
be connected graph. For instance, if you look at the induced subgraph of g on the vertex
set of v 1 or v 2 v 3 on anything v i in general, which should be an induced sub graph. This
was this was the concept of branch set.
Right and now let me remind you, what was a topological minor another one. Topological
minor. Topological minor means so let us say, suppose h is given. Now so this is an h. This
is a graph h and now, I can create a graph by subdividing this thing say h 1 can be created
by say i. I decide to subdivide this h that means so 1, 2, 3 right. This edge I have added
here and added a vertex and this is. So I can do it on another edge. I think keep keep
on doing it, right. It is possible that I can do it here. I can I can introduce a vertex
here. I have vertex here.
So, whatever graph we obtain by doing this thing, subdividing the edges is called t of
h right. So t h will call it t h. We will call it t h. If a graph g has a t h contained
in it, then we will say that the h is a topological minor of g. So it is contained sub divided.
We have discussed it before also, so I just wanted to remind. So, the famous theorem of
kuratowsky says, if g is a planar graph, if g is planar then, we cannot find any t h where
h is equal to k 5 or k 33. In other words, we will not be able to find out the t k 5
or t k 33 in g, if g is planar. It is an obvious thing because k 5 is a non
planar graph. We have already argued before, is it not? We have argued in the last class
that if t k 5 is not a planar graph. And now, if you take a non planar graph and sub divide
its edges, can it become non planar graph? It is not possible. Suppose, if k 5 subdivided
the edges and it becomes a planar graph, then why cannot the original one also be planar.
But, you can always contract it back. The same drawing will work with a little that
the in between vertices introduce vertices should be deleted and when we should use the
same the curve for the edge to denote it. So obviously, if we start with non non planar
graph and keep on subdividing its edges, it is not going to become non planar, so planar
right. So, as we have already seen k 5 is a non planar
graph. Right now, of case, with the it is with the the one theorem we had proved in
the last class, that a planer graph have at most 3 n minus 6 edges. So we may get, we
can get a different proof for this k 5 not being being a non planer. So because if you
consider k 5, it has, how many edges? k choose 2 sorry 5 choose 2 is equal to 10 edges while
3 n minus 6 if you substitute n equal to 5, will give us 9 because 5 into 3 minus 6 is
9 only. So it says any planar graph if 5 vertices can only have 9 edges in it. But, k 5 has
10 edges. Therefore, it cannot be planar, so another way of proving it right.
K 33, can we prove it? So, the same way, so the, for instance, there are six edges, six
vertices here. So 6 into 5 is 20 minus 6 is 14 but, we have only nine edges here. That
does not seem to work here. That same idea sorry so 33 18 minus 6 is 12 so which is little
more than, the same idea is not working. So we, but, we can we can refine the idea so
of 3 n minus 6 not in that k 33 does not have any triangle. Its smaller cycle is 4 cycle;
it is up to the, I can leave it to the student work out the detail. So k 33 so for instance,
you can use the Euler formula and then, where we substituted for the number of edges, that
so we we had substituted that 3 n by, so for each face is contributing 3 edges, we can
say 4 edges and then this will allow to sharpen the inequality for for this particular case
and then we can show that. So, that I leave to the student.
So here g is kuratowsky. Coming back to the kuratowsky’s theorem, we saying this obvious
2 graphs k 5 and k 33, so when I sub divide it and if definitely those cannot be planar.
So kuratowsky says, say in a planar graph, this cannot be there. Not only that, in any
non planar graphs, we should get one of this things; either this subdivided k 5or a sub
division of k 33, either t k 5 or t k 33. This is the very interesting statement that
is, it is a characterization of planar graphs right.
So to prove this thing, so we will in fact, we will prove a little slightly different
thing. We would rather prove that, it is nothing, one of one side it is very easier. As we have
already seen, that is, if t is a planar graph, then these topological minus 1be there right.
So then, if it is non planar graph this will be there. That is what we want to show right.
If it is non planar, this will be there, or in other words, if these minus are not there,
then it has to be planar graph. It has a plane drawing, that is a drawing on the plane without
the edges cross, this is what we want to show, right.
So, in fact what we will show is, if a graph just does not have a k 5 k 33 minor then,
it is planar is what we will show. So, it is equivalent because we will explain why
it is equivalent. We need not worry about the topological minor because if a graph if
a graph has no five minor, then definitely cannot have a topological k 5 minor. Also
similarly, if it has k 5 minor or k 33 minor, then equivalently we can say that it should
have corresponding topological minor. It is not true for every case. But, in this particular
case k 5 k 33 case, we can show that minor is enough because topological minor is not
very important. Because, we can we can we can say that if k 5 minor is present, then
k 5 or k 33 minor is present. Definitely, then k 33 or k 5 topological minor, one of
the topological minor is also present right. So that is the interesting thing about it.
Now let us let us remember some of the simple ideas, so which will helps to prove these
things. One is this, so suppose you you have a graph x with with maximum degree delta of
x less than equal to 3 right. Suppose, you have a graph x with maximum degree delta for
example, x can be k 33 right. This is why what we are interested in such a statement.
Then we say that if x is a minor of g, then x is also topological minor of g. So we will
we will look at this statement.
If delta of x is less than equal to 3, then every m x contains a t x. Thus every minor
with maximum degree at most 3, so also it is a topological minor is in it. How do you
show that? Because, what we are going to do is to consider a minor. So m x in fact, the
branch sets of that. So, you have this graph and then these are the branch sets right.
See the degree for, if I consider 1 vertex, the degree is only 3, and so maximum degree
is 3, at most 3. So, then you can you can take the minimum sub graph, in the sense,
that if some edges are not required in m of x, then I will throw away that. So, which
is essentially means that within the, within each of this branch set, the sub graph can
be considered as just a tree because because you do not need more than a tree spanning
tree for a connectivity. So that, just tree is enough and then this
tree is enough. Across each two two of these things, if there is an edge in x, then we
need only to keep one edge. So, there is no edge then do not have keep any. Otherwise,
you just have to keep one edge. Do not have to keep more than one edge. This is this is
minimizing the number of edges used in m x given in x. I am getting an m x, in such a
way that it has only the minimum number of edges in it, for creating a minor x.
So now, so the the point now is to observe that if this inside this thing so I can consider
a tree so you can see like this. So inside this thing, I can consider a tree and including
its neighbors in the other branch sets, just there are 3 neighbors. So, it may so happen
that yeah, so it is may be like this, just three neighbors.
So now in this structure you can you can go back to so see, you know, at some point these
two has to meet right. So it may be meeting here, somewhere and then, what about this.
This will meet somewhere here. This need not be, so it can be anywhere but, the third one,
wherever it meets, so you see three three parts going from here to here. So, essentially
we can delete all other things. We just need these things right. So these can be a long
path here. So similarly, in each of these things this structure will come.
So therefore, essentially if there is no, we can consider this vertex as a branch vertex
and then you can see this is essentially topological minor and not may not necessarily, so complicated
contraction are not necessary here. So that is why, we say that if x is a maximum degree
3 graph, the graph has only maximum degree 3, then if x is a minor of g, then x is indeed
a topological minor of g, also you can also see in this right. So that is one observation
we wanted.
The second observation what we want is the the, suppose I will show that if we have a
k 5 minor or minor or k 33 minor for g, then g has also got a k 5 topological minor or
k 33 topological minor. This is what we want to show. So why is this true? Is it following
from the earlier thing k 33? For k 33 minor, if there is k 33 minor by the earlier statement,
because k 33 is a maximum degree 3 graph, so k 33 minor implies k 33 topological minor
also but k 5 minor. Suppose what if the graph is only k k 5 minor. It is it need not be
k 33 minor right. If it is only k 5 minor, the maximum degree here is 4 not 3. So there
is no guarantee that so we will get k 5 topological minor also, but, what we are going to show
is if there is a k 5 minor then either you get a k 5 topological minor. If k 5 topological
minor is not there then there will be a k 33 minor and in turn therefore, a k 33 topological
minor; this is our planar.
So how will we do that? So this is the idea. So the idea is, so you just take the k 5 minor.
Its branch sets are considered. So the branch sets can be like this, 5 branch sets, 5 branch
sets are considered. Now again, the same idea of taking the tree. So we will, so we now
minimize the, this is an m x so and therefore, we will minimize the number of edges in the
m x. So for x is equal to k 5 and then m, so the therefore, this is here we get a tree,
tree like structure, so tree only. Similarly, here also there is a tree internally because
we do not need more than a tree for connectivity. Here we can throw away all the remaining edges
and so everywhere. Then you see, can also assume, that there is only one edge between
any pair because k 5 therefore, all pairs should have a connection between them like
this. But we can of case, we can of case get rid of the extra edges. We just need one edge
for getting a k 5 minor.
So, now what we do is for each of these things we have a tree induced here; we have one here,
one here and one here and one here. So this this tree along with this 1 2 3 4 vertices
can form, it will form a tree right. So it will look like this, some tree, and then we
have, yeah, can be some tree and then it will go. So thus tree is extended, so this is from
one branch, this one like this. So, now if you see that it is possible, that
you can you can go here, each of them go back and then, see they go back like this and then,
this also go back like this and meets somewhere and this also. At the same point, if all of
these things meet, so when I extend this edge to, so if it is so happen, there is like an
extended subdivided star right. So one star and then, elongated edges of this subdivided
star and it so happens, that everywhere its subdivided star. Then, we can easily see that
it is indeed a subdivided k 5 right. It is a t k 5 right because, everywhere we have
a subdivided star which is like elongated edges right.
So therefore, we can assume that one of them is such that, one of the branch set is such
that is not a subdivided star. If you, if you further four edges coming inside and then,
if you start getting the connection here and if you keep adding it here, so it will it
will so happens happen that the third one will not come and this this one will not come
and join here. It is in that case, it will again become a subdivided star. You can see
this right. It looks like this from the common point. So this star is a subdivided right.
So but, therefore, we we can assume that this will not happen. So, it will essentially go
to somewhere else, may be here right. Now let us take these two points, this point and
this point right. Now we can see that, so the contract this,
this, this and this. When we contract, so this will become one vertex right, one vertex
this, this, this will become one vertex. We will get a structure like this here. k 4 will
come here because, when we contract these things, they will this edges there across
therefore, a k 4 will come. Now, what we going to do is, we will take
these two as two vertices and then contract as much as required this branch, this branch,
this branch and this branch. So we we considering this vertex, this vertex and this, this, this
and this, we can see a k 33in it. And in it, we can see a k 33 in it because this is some
one side. Say a side, this is on b side and then this is on a side. We can put it these
two on a side and this two on b side right, so you can easily see that this is giving
a k 33 right. This is connected to this b, this b and this
b, this a is connected to this b and, yeah, this b and this sorry, this is, this a is
connected to b and this of case connected to b b right. This is connected to b and this
is connected to a b and b right. So you can see a k 33 in it; k 33 minor in it. We only
have to bother about a minor. We do not have to explicitly, so the k 33 topological minor
because in the k 33 minor, as we have seen already there is a k 33 topological minor.
This is the next idea I needed.
That the last idea before to prepare for a kuratowsky’s theorem is that, we need is
a simple statement. That if consider a plane graph which is two connected, any two connected
plane graph, so this is what we consider. That in any two connected plane graph, every
face is bounded by a cycle. This is what we want. So, this is also a simple statement
because, suppose we have a plane graph; Plane graph means it is drawn on the plane without
the edges crossing and it is two connected right. It is two connected.
Now, you can we just want to show that every face has a its boundary as a cycle, simple
cycle. So what we do is, we we first consider whether, this is the cycle node. If the graph
itself is a cycle, there is nothing to prove because essentially the face has to be like
this. So, it has to this cycle itself will be the boundary of the face, so we are nothing
to show. So one face is the outer face, one face is the inner face.
So otherwise, we remember there is a compositions. We will consider the last year or right theority
composition is keep adding, so the years of this sort right. So, because it is two connected
graphs, if there is a yearly composition. Assume that it is constructed by adding years
and consider the last year right, last year that is added. It can be something like this.
Now this is p path. This is an h path. This is h and this is this is p and this is together
by adding p on h we got g plane final graph. Now we know that this graph, this graph g
has a plane representation. It is drawn on the plane. We have to only bother about the
faces of it. Now if we consider a face of g and if it is also a face in h, we are done
by induction. By induction, we can say that this is the smaller graph. So smaller graph
we can assume that the theorem is true. So it is true.
So the only case we are bother about is the face of g which does not contain, which does
not contain, which is not a face of h right. If face of g, which is not a face of h, what
kind of face is that. So, it is definitely is a face of g somehow which involves the
path right, which involves the path we have removed the year. So, it should be finally
this path, this is path p it should be containing something like this.
Now, you see this path right, should be containing, so when we remove this thing, so because the
the other the the this this area is part of some face of h. Then therefore, it should
be containing some face of h like this. Listen. So like this and then there is totally inside
this face right, is it not? Because, we cannot cross.
So this this path, the interior region of a path has to be internal to face in g. Now
if I add this thing, naturally this face also has to be a cycle right. This is a simple
idea. Therefore, 2 connectivity means that any face has a boundary which is a cycle,
this the last thing we are going to do. Now, we will look at one special case of kuratowsky’s
theorem, namely, will show the if the planar graph is three connected, then it is if the
planar graph is three connected, then it has a, sorry k 5 minor or k 33 minor right. So,
or in other words so, in other words sorry, we are going to prove that a non planar graph
which is three connected right. Sorry, our strategy will be to prove that if a graph
has k 5 minor or k 33 minor then, it is non planar. First, will show that if a graph is
three connected and without a k 5 or k 33 minor, then it is a planar. To show, so this
is the statement. So three connected, sorry I do not have this idea.
So yeah, if the graph has so these are the properties, g is three connected and without
a k 5 or k 33, minor then it is a planar. After that, we will remove the three connectivity
requirement and then we will argue it simply right, the connectivity.
The k 5 or k 33 minor free graph, which is three connected. So we will remember result,
that in any three connected graph, there is a edge x y. edge x y So three connected graph
edge x y, such that if contract, this edge x y we will end up with a graph, so we have
the contracted vertices x y. So after contraction, we can get a graph such that it is still three
connected. This is what, so this what we studied right. So we will use this theorem. Then,
we will look at the the edge x 5, which can be contracted without losing three connectivity.
Let say x y is the edge and then, v x y is the edge which is obtained after contraction
right. So, the point is again, we are planning to
use induction on the number of vertices. If you if you know that for all smaller graph
which are three connected, without k 5 minor free and k 33 minor free, it is planar right.
Then, we will show that this graph with one more vertex is also like that. Here, what
we have done is to reduce the number of vertices by contracting the the edge. But, in the process
we also retain three connectivity because, we selected the edge to be contracted carefully
because we use them. The earlier result which we proved as part of connectivity when we
studied connectivity, that there exists an edge which can be contracted without losing
three connectivity. So we did not use the connectivity but, reduced
the number of vertices. We reduced the number of vertices. Before we can say that, so the
so the smaller graph is three connected. Can it have k 5 minor or k 33 minor? Of case not.
Because after contracting, if k 5 minor or k 33 minor appeared then already the original
graph also had k 5 or k 33 minor. So by contracting, it cannot produce a k 5 minor or k 33 minor
which is not there before right.
So therefore, the the after contraction we got a smaller graph on which we can apply
the induction. That means, it is three connected and without the k 5 minor or k 33minor. Thus,
we can assume there is a drawing of that graph on the plane. It can be something like this.
So we, so most important thing is to locate the vertex v x y and then because we have
some is a three connected graph. Even if you remove this vertex v x y, it will be still
a two connected graph because if you remove one vertex from three connected graph, its
connectivity still be at least two. Then in a two connectivity graph graph, every face
is a cycle. So we can see the face of that graph, so g in this. When I remove this vertex
v x y in the remaining graph, which is two connected, the face which contains v x y,
this point v x y so that it will be a face. We can see that the neighbors of v x y, which
is essentially the original neighbors of x and y together has to arrange them in such
a way, right, in on this face in a circular way.
Now what we do is, we suppose we just want to call v x y as x and remove all the neighbors
of y which is non neighbors of x, then some some neighbors we have to delete from here.
Say may be, yeah, so like that. Some of the exclusive neighbors, so only the x neighbors
were present here. So we can call it x 1 x 2 x 3up to x k x k.
So, this this will cut it into several regions, x 1 to x 2, and x 2 to x 3 like that, cut
it in to several regions right. Now, so the question is where are the neighbors of y?
For instance, if the neighbors of y were here, then all of them all of them are in one region
like this. Then, I could place y here and connect it here and then make connection like
this here. So, that would that would allow me to represent g also right. So, that will
that will prove the proof of the theorem that this is so, g also is represented by. So,
we will look at the complete proof in next class right and complete the proof in the
next class. Thank you.