Tip:
Highlight text to annotate it
X
Welcome to the thirty-ninth lecture of graph theory. In this class, we will look at graph
minors; of case, we are already familiar with graph minors; I have talked about minors earlier
also. But in this class, we will look at it in a little more detail, of case we do not
have much time to go in depth, we will just touch some of the initial material of this
subject. As the student should be already familiar, these are the three operations involved
in taking minors.
Contract an edge, which means if there is an edge like this, so these are the neighbors
of it say says some neighbors like this also, then you decide to contract this edge; what
will we do? We replaced this with one vertex, new vertex, and all these neighbors will become
the neighbors. All these neighbors, all these things will become the neighbors of this new
vertex. So, of case, you may see that like, they are two edges here that may become multiple
edges, but then we can discard one of them, if multiple edges are not relevant. So, the
contraction operation is this; any way, we are already familiar with it, so do not go
into again repeating it. So, delete a vertex is the second operation, delete an edge, so
you can do it in any order, and in any number of times and whatever graph results is the
minor of the original graph, this is what we told.
Let us presently slide frame, because so we want to concept called branch set. So, let
G be a graph. Now, if X is another graph, and corresponding to each vertex of X, X is
the smaller graph, let say compared to G, X is the smaller graph. Corresponding to each
vertex of X, we identify a set of vertices of G, so that is what V X. For each X element
of V of X, we identify V(X), namely some subset of the vertex set of G, and get this collection
be a partition of the total vertex set of G, V of G in two connected subsets.
The property that we need is each V X should induce some connected graph in G it is a connected
subset such that and another property we need is any two vertices in X in the smaller graph
are connected or adjacent you cannot only if there is the corresponding edge between
V X and V X. So, that V X V Y edge in G that is we say that then we will say the G is a
M X and write G equal to M X, so then the these V X are called the branch sets of M
X.
So, we can take an example and so let us say so let us say this simple graph, so we can
right so this graph so let us identify some collection of connected vertex. So this is
one collection, this is another collection and this is another collection and this is
say another collection right. So, this so this is some vertex and just marking it of
so here, so essentially I have partition the vertex set of G so this graph, the red graph
is G red graph is G and I have partition the vertex set into say this is 1 2 3, so this
and then this is 4 5 6 7 is another group, 8 9 10 11 is another group, 12 13 is another
group now you can corresponding to this. So, we can mark a graph like this. So there are
1 2 3 4 vertices so this is M X 1, see this M X you can see this vertex A correspond to
this A, B correspond to this B, C correspond to this C and D correspond to this D right.
So the point is corresponding to each vertex here we have a subset of vertices of G and
then they are connected each of these subset are connected for instance here there is connectivity
here there is connectivity, here there is connectivity, here there is connectivity and
then now whenever there is an edge became these two, if there is an edge between these
two, there is the edge between the corresponding sets here here between C and D, C and D C
is this, D is this. So, the vertex are edges between that not necessarily one at least
one is what we are say right, so this is vertex so then we will say G equal to M X, so this
and then C of case that are many G which are M X and this G is also M X and which other
branch sets here? These are the branch sets these these these are the branch sets was
X correct.
And then the point is that G, G can be seem as M X only if X can be obtained from G by
a series of edge contraction that is that see it you understand for instance, if I contract
these edges here this will this can become this vertex vertices, and then if I contract
these edges then this will this vertex will come, if I contract these edges edge this
vertex will come and contracting this four edges will results in some multiple edges
will be there what we can discarded. So, then so by a series of edge contraction I can get
this thing and also it is very easy to say that see that, if from G you can if there is a series of edge
contraction to get this thing, we can always identify the branch sets there essentially
the vertices which code contract into one vertex of X they from the connected set right.
And also the vertices which code contracted into one set will not be part of the set of
vertices it code contracting than other one; therefore, this M X idea and this contraction
idea its equivalent right, it is are same. Therefore, we can view it the idea of minors
this contraction in two different ways: one is thinking of the graph minor sorry or or
the smaller graph as obtained as the result of contraction, the other is we have the identify
the branch sets. And then there the part on of adjacent set these between the subsets
is captured as a smaller graph that that both way its same its equivalent.
And of case then we have the notion of the illusion of the vertices illusion of edges
to accommodate that we will say G equal to M X is a sub graph of another graph Y, when
X is a minor of Y is not that we need to obtain X from Y by a series of contraction along
we can also delete some vertices. And edges if you want to accommodate that we will say
G equal to M X if G, such a M X is sub graph of some other y and then X is the minor of
Y so this what? So, now let us look at some examples I am
already explain what some some an example here, so far instance we can ask in general
view we will usually ask what is the biggest clique minor that we can obtain from a given
graph, why this clique minor is an important, because if a clique minor on some k vertex
is available in g then every graph on at most k vertices is available in G right. So, because
the edge illusion, vertex illusion will allow as to get the smaller graph in its; therefore,
the clique minors are usually studied, so and also then see lets that is also easy to
understand.
Therefore let us ask the simple question suppose it is a tree G is a tree what is the biggest
clique minor that we can get, so we have probably we have mention it before this biggest clique
minor that we can get from a graph G is denoted by eta of G, and its sometimes called Hadwiger
number. So, which will be clear later, because its associated with the Hadwigers conjectures,
so that is why it is called Hadwiger number that we are going to explain a little later.
So, let us see from given a tree in a tree, so what will be the Hadwiger number of such
a tree, so the question that definitely you will immediately see that you can get k 2
as a minor clique there are some edges. And then so you do not we do not even have
to contract we just have to delete other edges, and the vertices just to take this thing,
but then can we get a k 3. So, the crucial thing that we have to see when if you contract
any edge here we contract any edge here so we what we get is again a tree; therefore,
as we contract the that that tree property will not be lost it will be tree after contraction
it always will be a tree. So therefore, we will never generate a cycle from that therefore
k 3 will never come, so k 2 is the biggest clique that we can get from this thing eta
of T is equal to k 2 for in a tree.
Now, see one interesting observation that we can make is that the similar kind of thing
is true for planar graph for instance, if we take one planar graph and what will happen
if I contract contract an edge here, so far instance this is a planar graph, so I can
contract any edges you can see the planarity will be suppose will be maintained for instance,
if I contract this then what will happen? So, I will replaced with one vertex here,
so not here, so you can I can replaced it here itself, and then this this can be drawn
like it without without destroying the planarity or for instance. If you are try to contract
it what will happen, so this so you can place vertex here, so this entire thing will come
here, so the planarity will not be lost right, so that you can imagine as shrinking the edge
slowly and everything get closer. So because we are within in a face, so it is not going
to effect the embedding the planar graph in the plane; therefore the planarity is mentioned
if you contract edges.
So therefore, the what will be the what can I tell about the Hadwiger number of planar
graph, definitely you can say that the for any planar graph eta of G the biggest clique
minor has to be less than equal to 4 right. K 4 is the biggest you can get why is it so
because, if you get a K 5 or more from the planar graph by contracting that means that
because the contraction operation retains the planarity property if K 5 is obtain by
contracting edges from a planar graph, K 5 also has to be a planar graph, which is not
true K 5 or more cannot be a planar graph therefore, the biggest clique minor that you
can get from a planar graph is at most K 4, biggest is K 4 you cannot get K 5 or more.
So from a cycle what we can get is a triangle, and that is very easy right for instance you
can you just have to keep contracting, and then you will end up with the triangle, then
right this are some example of taking minus using contraction. Now, let me ask one question
for instance can we see any relation between the biggest clique minor that we can generate
from a graph and number of edges in the original graph, so the answer is also clear in fact
as we contract the edges of the graph. What we see is then number of edges can never increase
we lose some edges, we never increase the number of edges because if you contract what
we do not add any edges right, we do not any new edges, the old edges only become slightly
reposition because two vertices become the same vertex by getting merging together right.
So the number of edges can only decrease.
Suppose, if m was the total number of edges before so then suppose if K t is the biggest
clique minor you can get, then we know that t into t minus 1 by 2 has to be less than
equal to m right. Because you cannot generate in m any new edge, so from this thing we get
t into t minus 1 less than equal to 2 m, and we can get some upper bound 4 t in terms of
m something like root 2 m will be so little from this thing we can get right. So, the
therefore if the number of edges is very small, so there is the we cannot expect very large
minors of case, so it can be much, much smaller than for instance in the tree there can be
n minus 1 edges, but so we always get maximum K 2 minor right. We can never get planar graph
can have at most around three n minus six edges, but still we can get only a K 4 minor
from that maximum, so not more than that. So, therefore of case this is just easy upper
bound, and another thing is to look at the idea of branch set to demonstrate how to see
the view the minus as branch sets.
Let me take this example so this is what it is called a grid, so this is an n by n grid.
So essentially n by n grid is the Cartesian product of paths, Cartesian product of P n
P n cross P n, so then suppose I make a copy of this. So, say something like this right,
so then so and also connect if this, so that means
this is called a double grid. So, essentially formally this is the formally this is the
Cartesian product of two paths P n into P n into an edge K 2, this is what now I am
interested to show that we can get a K n minor from it K n clique minor in it, so n clique
minor in it, so that do this thing, so this is the technique. So, we can so I am just
marking some branch set, so for instance I will take this and this one branch set; that
means this one column from the green grid and one row from the red grid so the first
row, and the first column first row of the green grid and the first column of the red
grid. So, you see that this this row is connected here, this column is connected here, and also
because of this edge. This entire thing forms a path, so here up
to here it can come and then now it can jump here and then this is full path this is the
connected set. Similarly, we can take the second row of the red grid and the second
column of the green grid, and because of this connection the entire this is this two are
connected in that that forms a connected. Then we take the third row, and third row
of the red grid, third column of the green grid and that forms a connected set then like
that we can get n branch sets there all connected and they are disjoint also it pair vice disjoint.
Now, if I contract them what will I get that is the question, now to see this thing, so
we can what probably we can we can make to it in a smaller step. So one there is, so
let us let us define the branch sets slightly differently so it takes correspondingly each
red row, we have the branch set its send definitely connected corresponding to each green column
we have a branch set.
So, that means we will get a graph where is these are all red column n n of them, and
similarly, here we have green, this is red rows corresponding to each correspond to a
red row, and this each correspond to a green column. And then of case we know red row intersect
with each green column; therefore, intersects means that there is an edge between them.
So for instance, if you have a red row like this so the green columns are green like this
right. So, then we have the connection, so another will be going like this, so you have
this connection, so another will be going like this you have this connection.
So therefore, smaller connected so we will get this graph of case there are other connection
between them between them, but then let us discarded for the. Now, we can merge dimension
before we can merge these two vertices together that means, so originally we are seeing. So,
this is what this is complete bipartite graph k n n, and then if we merge this this this
this together that means is correspond to the first row this the first column, this
is the first row here, the first sorry second row here, second column here, is the third
row here, and the red and the third column in the green, if we merge it what will we
get? We will get a k n right, because if the complete
bipartite graph there so this is connected all these sides and this is connected all
these sides. Now, in the all become 1 1 one of them so they will they will have connections
between every pair, so we get a k n n. So, here we see the concept of branch sets more
clearly here, we can see what is become k n the each vertex of k n can be interrupted
as a column, and row a red column and a red row and green column, and because the branch
set, because they connected and when we contract them we will get this get this k n.
Now, so this is just we let us try to some of the this thing and another concept you
have to look at is the topological minor, suppose you are given a graph X with and then
we replace each edge of X it independent path between ends. So, we call the graph G obtained
a subdivision of X, we have seen this before also like which has to take an edge and replaced
with some paths which are the number of edges in the path is depending on how many times
it divide, and this is such a graph is called T of X. T X, so if t s is a sub graph of Y
then X is a topological minor of Y, T X is a sub graph of Y then X is a topological minor
of Y.
So for example, we can we can see that, see for instance, so this is of case this is a
cycle and that triangle is a X and this is G. So we can three vertices to this, so this
edge can be seen as subdivided here and this edge can be seen as subdivided like this and
this edge can be seen as subdivided like this. Of case we can have other edges here, but
because we only want that is T X of big cycle was T X, and then T X should be a subset of
this, then we say that X is the minor of these entire graph sorry topological minor of these
entire graph. So of case if X is a topological minor of
y x is definitely minor of y minor of y also y because topological minor means we can of
case take the some, and we see that definitely we can contract the edges of the path and
get X right. Therefore, if X is a topological minor of Y then X is definitely a minor of
Y also the other way need not to be true for example, we see that these vertices are called
the corresponding vertices right. We have any corresponding to each we have to fix a
vertex here sorry, this this three vertices we had fixed. These vertices which correspond
to the vertices of this thing right before subdividing the path, so those are called
the branch vertices equivalent to the branch sets.
So these branch vertices, because if the degree here in x is 2. So, two path should be going
lot of here for in general if the degree of the branch branch vertex is k n x, but we
should see k path at least going out of this thing, so the degree of this thing should
be at least as much as that. So, it is not possible to get for instance for if G is a
k regular graph it not possible to get k, k plus 1 regular graph as a topological minor
of G because, we see this a requirement but on the other hand the minor is different it
is possible that we can get the denser graph like this some minor. So, even if for instance
we are getting complete graphs big complete graphs, we can get as the minor even if the
original graph as path as long as there were number of edges were enough. Then the contraction
allowed us to accommodate edges in the same vertices degree can increase by contraction
while here subdivision operation cannot increase increase the degree right; therefore, that
is clear.
But on we can see that in some very special situation the reverse is also; that means
if we have a minor that means if we can identify branch set corresponding to given X, then
we can also have a topological minor. So, its happens when delta the maximum degree
of X is at most three, so how do you do this.
So to see this thing suppose you have we had identify this branch sets, some branch sets
for X so these are the vertices of see x 1, x 2, x 3 correspond to these branch sets you
know we need connectivity here, we can discard all other edges, just keep a tree here, because
you know we can discard other edges, once we retain connectivity it can each branch
set right. So, let us say this is minimal number of minimal edges we need from G, so
that connectivity is there and also suppose, because whenever there is a connection between
the two vertices here, edge between the two vertices they should be corresponding edge
between this. For instance, we can see this this may have
at most three connections outside, so let say we include this vertex take this vertex
also and say take this vertex also, and then now look at this tree, this again a tree this
thing now, because it is a tree. If we see that between this, and this we have a path
unique path, and then this will joint it somewhere somewhere right. So, if you take so it is
easy to see now that will be one vertex such that you can see paths going out of this,
and this and this right. Now, everywhere if you replaced like this
then you can see discarding other edges unnecessary edges which not taking path this thing, we
can see topological minor we can see it, T X its next contain the T X that is what, but
that this happen only even delta is at most three it is it not happen a when delta is
greater than three. So, now the the next, so before went to the next topic, so we can
illustrate the idea of topological minor by taking one example from.
So far instance, which one example for from what we have studied earlier, so far instance
look at this graph H d h t which hyper cube - d dimensional hyper cube, essentially remember
that this is the graph whose vertex set is 2 H d vectors, d length vector like the vectors
are like 0 1 0 1 like the 0 1 vectors. So, the width d components in it, in the 2 H d
of the other, and when other connected 2 vertices are connected with an edge adjacent with an
edge when the hamming distance is 1; that means when they the corresponding vectors
differ in exactly one component position. So we have familiar with hyper cube, so then
what is the the biggest topological clique minor that we can get in which what is the
biggest n such that K n is the topological minor of H d, so this question. So, immediately
we can say that n has to be less than equal to d right sorry n minus 1 has to be less
than equal to d, because here H d the degree of each vertex is d right. Now, k n means
they are n vertices right so degree is at most d, so the if if you take K n then we
have a n vertices in it, the degree of each vertices n minus 1 so the n minus 1 cannot
be more than d as we have already mention, because from every branch vertex. We should
we will see at least n minus 1 path path going only d path can go, so we we can they only
at most n minus 1 path. Now, let us also see a topological minor here,
so take this vector so far instance one as 0 0 0 0 this vector, and the other is 1 0
0 this vector, the second is 0 1 0 0 0 - this vector and finally, we have the dth vector
namely sorry d plus 1th right d plus 1 th vector is this 1. So, here this is 0 0 1 this
is corresponding to each bit position we just keep 1 all of the 0 so and greater than 1
vectors, and then now I want to show that this vertices formally topological minor.
Of case this this central vertex, this vertex, 0 0 vertex is a connected to all other vertices
all other d vertices that we have, because the hamming distance is just 1 for all of
them, and then how do show that between any pair of these two vertices.
For instance the 1, so let us take one vector a 0 0 0 i th position, we have 1 and all others
are 0 here, and take another vector where jth position we have all these place, we have
a 1 and then all others are 0. So of case so what we can do is we can identify vector
here, it is adjacent to both namely it has in the ith position and jth position we have
1, all other position we have 0 right this is definitely adjacent to this vector because
the hamming distance is just 1. Similarly, this is also adjacent, and then clearly there
is an path between this and this, and this intermediate node will not be path for any
other i j, because this ones appear in the ith position. And the jth position for any
other pairs two position will be different; therefore, we see that there is a d plus 1
K d plus 1 topological minor here, and then that is the best that is maximum possible
you cannot get anything greater than this, so this is clear.
The now we will come to of case this was just introduce this concept, the minus the topological
minor we just worked out some examples to understand how this what this topological
minors are and what the clique minor sorry, usual minor are and we also looks into the
clique minor which are of case easier to understand, because between every pair we need an edge
every branch set we need a edge. So, this Hadwiger conjecture can be easily understood
now, so this is one of the most important conjectures in graph theory, and its try to
extend the four color theorem, the this question this this conjecture say for every integer
r greater than 0 every graph G. If the chromatic number is greater than equal to r then it
should have k r minor, the graph should have a K r minor if the chromatic number is at
least r. So, the in other words if it does not have a K r minor then we can color vertices
of the graph properly using at most r minus 1 colors. So it is why easy to verify for
small cases for instance.
Let us look at r equal to 1k, that means if the chromatic number is 1; that means it is
isolated vertices it do have a K 1 minor then r equal to 2 k’s that means the of case
we are saying that if we denote have a K 2 minor, so that means if you denote have a
K 2 minor we should be able to color using one color definitely true, because if there
is no edge we can color using. So, of case so r equal to three k’s means, so this is
not for so this is r equal to 3 k’s means if there it denote have a K3 minor if it denote
have a K 3 minor. Then we can color using two colors 2 colors, so if you denote have
a K 3 minor we can color using three colors so this is very clear because, if you denote
have a K 3 minor, but we do not even have a cycle in the graph for the trees we can
colored using two colors. So what about the next if you denote have a K 4 minor, then
r equal to 4 k, K 4 minor then we can color using three colors, so sorry we color using
three colors r equal to 4 k’s right.
So, this can be so this needs a little more effort, so this this we need to understand
the structure of the graph without a K 4 minor, then if we denote have a K 4 minor we need
to show that it can be color using three colors. So to do this thing we have to understand
this structure of the graph without K 4 minor, so this helps here is a graph with at least
three vertices is edge maximal without a K 4 minor if and only if, it can be constructed
recursively from triangles by pasting along K 2 s K 2 s the K 2 means edges. So, just
K 2 s why we will look at it edge maximal graph, so we are interested in coloring graphs
without K 4 minor, we want to show that a graph without K 4 minor can be colored using
at most three colors. So, instead of generally looking at any graph with K without K 4 minor
we are same that we will look at edge maximal graph without k 4 minor with the property,
there are no K 4 minor, what do I mean by that, I mean that I keep adding edges in such
a way that still in K 4 minor. So, we come to a situation saturated situation
namely any more edge in adding one more edge will introduce a K 4 minor will introduce
the k 4 minor in such a case, we will have to… So, we will say that it is an edge maximal
graph with the property, but there is no K 4 minor. So, it is enough to show that this
kind of graph can be colored using three colors right, because if this kind of graph can be
colored using three colors any graph without a K 4 minor can also be colored using three
color, because give me a graph without a K 4 minor than I can always add edges to it.
And make it edge maximal with respect to this property of not having K 4 minor, and definitely
I have only added edges after adding a few more edges, I can color the graph with three
color the original graph also can be colored using three colors, so that is why we are
looking at the edge maximal graph along. Now, so this gives a structural description of
that this type of graph edge maximal K 4 minor free graphs, it sense that if they exactly
added graph which can be constructed move from triangles by pasting triangles recursively
along K 2 s something like this.
So we can, so we start this is one triangle, of case this is a edge maximal K 2 minor free
so we can add a triangle so we can identify this edge we can paste one of the triangle
along this edge. So, now this a new graph so we can of case we can another triangle
and then say identify an edge may be as this one, this one, in then I can paste one here
this triangle for I can paste another one here like identifying this was the edge to
paste or we can identify this edge once again. And then paste one triangle here, so I can
paste one here, now we can paste one here, so this way so I can paste one here is identify
this edge, this this kind of graph are called so that graph which are obtain by pasting
triangles recursively so, we are we are not along to paste like this right because, that
is like identify a vertex alone. So, what identify edge it paste, now why do
we thing that this graphs which are edge maximal without K 4 minor, of case they cannot be
a K 4 minor here, so if there is a K 4 minor and suppose up to here up to some stage, we
do not have a K 4 minor, and then we suppose decided this edge, and then we pasted it triangle
here. Now sudden a K 4 minor appeared, so how will
the minor look if k 4 minor appear because, a K 4 minor has maximum degree of K 4 is less
than equal to three right is three only. In fact therefore, then they should be a K 4
topological minor also right, so is it possible to have this is a branch vertex here, if this
is a branch vertex the new one, then the other one has to be the other three has to be somewhere
here right inside 1 2 3 somewhere here in this portion, but then there is only the two
edges going out of this thing it is not possible to half this branch vertex. Now it should
be all the branch vertices should be here, but then what is the use of having this, we
have we can instead of going why are this we could of always use this edge.
And then we will get that K 4 topological minor in the part itself. So therefore, that
would be a contradiction that inductively, we assume that earlier they was no K 4. Suddenly
K 4, minor cannot exist in the new graph, and also its edge maximal because, here it
is was edge maximal. Now, if this is not edge maximal the edge that we can add without introducing
a K 4 it has to be something like this. Now, clearly you see there is already a triangle
here there is already at triangle here, and this edge if you contract this entire remaining
part will give us the the new K 4 right, so because they should be some connection between
this, and this here right. And then also there is a some connection here. So therefore, I
so we can we can prove that we can we can get a if such a if it is not, if we can add
an edge without introducing, so we we cannot add any edge without an introducing a K 4
minor. So therefore, this is edge maximal K 4 minor graph definitely that is not the
key issue, the issue here is essentially, so these graphs are indeed edge maximal with
the property that there are no K 4 minor in it is, but any edge max what we want to say
that any edge maximal graph without K 4 minor will have this structure namely the obtainable
by pasting triangles on K 2 s right recursively. And how do I proves that so to to show that
so we just need required easy, but I will just start it of but will not do it completely,
because we do not how much time now so to see this things, if we can see that suppose
we are given an edge maximal graph without a K 4 minor.
Now, can it be a complete graph know if its complete graph it has to be K 3 only, because
only three vertices should be there, but if it is a three vertices then definitely it
does not have a K 4 minor. So therefore, at least four vertices then it cannot be a complete
graph, of case if it is just a triangle, we are through, because it is one triangles like
we say it is it is pasting of triangles. And what show whatever as we as we required it
is it is one triangle, but if it is more than a triangle that means four vertices are more,
then we cannot have it a complete graph, because then K 4 minor is anyway there, so it is not
complete graph; therefore there is a separator.
And then this separator cannot be too big, if it is three or more. So let us take two
components right now some vertex this components, and some vertex in this component say v 1
and v 2, so they will three paths disjoined path between them right. Internally because,
of the connectivity, because of the minimum separator we consider so with connectivity
is three or more they should be three length path. Now, suppose if I had removed these
two vertices still the graph will remain connected, because the minimum separator size is three
by removing just two vertices, we cannot disconnect the graph.
So, we can assume that there is one more edge say between one more path between this, and
this so between any two of them. So, one pair we will still get some connection let take
this thing, now taking this this and this vertex right, so we already get a K 4 minor
and this, this vertex so we have a K 4 minor here. So right is the triangle, and so this
vertex is connected to this, this and this so we have a K 4 topological minor here. So
therefore, we can see that that is not possible to have now we can assume that the connectivity
of this graph is K 2 or 1, so and then we can analyze again based on the edge maximality
and K 4 minor and then show that it is it will it will lead to the contradiction, so
I will leave it to the student for working that out. So, we will the point is anyway
we need not worry too much about the proof of that it, because easy so of case some technical
details that is all.
So, we we will go to the next statement, what we will what this means is that one of the
implication is that see then any edge maximal graph without a K 4 minor has at most 2 into
number of vertices minus three edges, why is it? So, this is also a simple induction.
Because you know it start with a triangle, only three edges for three vertices that is
three n minus three put n equal to 3, we get three right, so that is correct. Now, if paste
another triangle, so what do you you are introducing in one more vertex, but only two edges right,
so that is like here we are introducing; of case so 3 into n plus 1 minus 3 equal to three
n minus 3 n, 3 n edges is what we are expected have by the statement, of case we are only
increasing two edges here, so we are not increasing three. So, right for instance the four vertices
is what how much we have so four vertices three into four sorry the number is wrong.
So 2 n minus 3 edges what we need, so this is wrong.
So, the what again we want to show that 2 n minus 3 edges right, first let us first
let us let us for the triangle, put n equal to 3 so 2 into 3 minus 3, so that is 6 minus
3 equal to three that is correct. Now when I am when I am pasting a new triangle so we
introduce two edges that is becomes 2 into n plus 1, and and this minus 3 that is for
for every new vertex here only introducing two edges, so this will be true; so this by
simple induction it is its verified. Now, so that was just some consequents and immediate
consequents if there is no K 4 minor in the graph then the maximum number of edges, you
can get in such a graph is 2 n minus 3 where n is the number of vertices.
So the point now is Hadwiger conjecture will holds for the r equal to 4 k why it, so because
you know the K 4 minor of graph is a K 4 minor of graph I want to show that it can be colored
using three colors. So, what we do is we add edges, and make edge maximal, because if the
edge maximal maximal graph will be colored of case the original graph can be also colored.
But this edge maximal graph can be constructed by pasting together the triangle, so this
is like a just pasting together the triangle now this is colored using three colors, now
when you add one more vertex, one more triangle, so definitely so this color, if we gives to
the two vertices. And then the third color given to that which very easy to see that
always this edge maximal graph can be colored using three colors, so the Hadwiger’s conjecture
is to for is 4 K; that means when 4 K minor is not there it can always color using three
colors.
Now then next case is when K 5 minor is not there the sit, we want to show that Hadwiger’s
conjecture in this case, we want to show that any graph without K 5 minor can be colored
using four colors. See of case, so this is requires as structural theorem like this we
need to understand this structure of the graph without K 5 minor, it is provided by Wagner
in 1937. Again we only on to consider the edge maximal graph without K 5 minor and he
told it characterized the graphs without K 5 minor, and edge maximal with respect to
the property. So, he says let G be an edge maximal graph without a K 5 minor if G is
greater than equal to 4 then G can be constructed recursively by pasting along K 3 triangles
and edges k 2 s from plane triangulations and copies of the graph W, what is the graph
W?
So, this graph W is a special graph which is eight vertex graph 1 2 3 4, 1 2 3 4, 1
2 3 4 5 6 7 8 so and then there is connection between these two and there is connection
between these two, and there is connection between these two, and there is connection
between these two, this graph is called W, say eight vertices on it. It can be drawn
in several different ways, but let just because we do not have a that much time we will just
take this drawing, so this is a special graph so he says take this. This is non planar graph,
but this is only non planar graph had to bother about, when we are considering the edge maximal
graph this non planar graph. And other than that any edge maximal planar graph that means
the plane triangulations, edge maximal planar graphs are essential the plane triangulations,
why because when keep keep adding when when you add an edge.
And if you lose planarity then K 5 yeah, so the that is not direct need the proof of that,
but because on K 3 3 the K 5 minor make them, but so we he proves that so in that case including
this thing.
We can make sure that that is only we need bother about only plane triangulations and
this particular graph, so these are the edge maximal cases we can what we can do is we
can paste them along like in the earlier case, we had pasted along K 2 s that edges now we
have to place along paste not only on K 2, but also on K3 if necessary, if two kind of
pasting are allowed on triangles we can identify a triangle in this graph, and then in the
graph. And then and merge them together by putting the vertices of the identifying the
vertices that triangle in both the graphs, so are like we did in the earlier case, this
is the only way we get edge maximal graph without a K 5 minor.
And from this thing you can immediately conclude two things: One is how many edges will be
there a graph with n vertices is no K 5 minor has at most 3 n minus 6 edges the same kind
of induction, we did here it little more complicated calculations are required, but this is by
induction we easily to this thing. And the other thing we conclude is that Hadwiger’s
conjecture Hadwiger’s conjecture holds for r equal to 5 K; that means if K minor is not
there we can always color with four colors, why because each other components. That means
we are constructing this graph edge maximal graph without K5 minor graph will plane triangulations
which are obviously colorable using four colors by four color theorem.
We have already studied that and this particular graph this this graph this graph definitely
can be colored using four colors, and now we are pasting only on the triangles or an
edges. So, when we pasting we can rename the color in such a way that the both the both
sides are consistent. So, this technique is very easy I leave this student, leave it the
student to verify; therefore, in this case also it shown that the Hadwiger’s conjecture
prove it.
Now, the next case proved by Robertson Seymour and Thomas in 1993; that means if K 6 is not
there you can color it with five colors base by extending the four color theorem. We uses
the four color theorem for the purpose of this thing they uses, so but it is considerably
more difficult.
So that is all about Hadwiger’s conjecture, so there are some other special cases also
like proofs is result. So, we will continue in the next class.