hey everyone got a nice short little lesson for you today we're just going to be introducing the concept of complete bipartite graphs I think we've already talked about complete bipartite graphs in some of my previous lessons and we will certainly continue to discuss them more in future lessons so might as well go ahead and make a video just dedicated to explaining what these are assuming you already know what bipartite graphs are complete bipartite graphs are just bipartite graphs with every possible edge so let's explain that in a bit more detail to make sure there is no confusion so let's say we've got a graph G with vertex set V and edge set E we say that G is a bipartite graph if there exists a partitioning of its vertex set into two sets we could call v1 and v2 such that every edge of G joins a vertex in v1 to a vertex in v2 or equivalently no edge of the graph joins two vertices that are in the same apartheid set that's what these sets are called partite sets and again this is a partitioning of the vertex set so the vertex set V is equal to the partite set V 1 Union with the partite set V 2 to say that this is a partition of the vertex set means that every element of the vertex set is in exactly one of these two-part tight sets so they have no common elements and again I'm assuming most of you are already familiar with bipartite graphs so let's jump into an example we'll see a bipartite graph and see what it means for that graph to be complete so here we've got six vertices that I have colored in two different colors now I'll just draw in some white edges joining some of the orange vertices to some of the green vertices so this graph we have just drawn is a bipartite graph it's got six vertices and clearly we could partition its vertex set into two part tight sets V 1 and V 2 where we see every edge of the graph goes from one part tight set to the other every edge joins a vertex from one part tight set to a vertex in the other part tight set and so each of these part tight sets is called an independent vertex set because it's a set of vertices where no two vertices it contains are adjacent now of course not every bipartisan in such a way that it's obvious it's a bipartite graph but this helps clarify the concept now is this a complete bipartite graph because that is of course the point of this lesson no this is not a complete bipartite graph why not well because it doesn't have every possible edge in a complete bipartite graph not only does every edge join a vertex from one part tight set to the other part tight set but additionally any pair of vertices in different part I'd sets must be joined by an edge in a complete bipartite graph and so it's very similar to the idea of a normal complete graph it's just a bipartite graph with every possible edge so to finish making this a complete bipartite graph we'd have to join this vertex to this vertex go ahead and do that and join at this vertex to this vertex go ahead and do that and lastly join this vertex to this vertex get that last edge in there in this case you might notice that the graph is three regular each vertex in this graph is adjacent to the three vertices in the other part tight set that of course would not be the case if we say deleted two vertices from one part tight set now this graph is not three regular all of the vertices in one part tight set are adjacent to the one vertex and the other part tight set so they all have degree one but the vertex in the other part tight set is adjacent to all three vertices in this part tight set and so that vertex has degree 3 then in general of course in a complete bipartite graph the degree of vertex in a part I set will be equal to the cardinality of the other part tight set there are three vertices in this part tight set this vertex is adjacent to all of them and so it's degree is three we have some nice notation for complete bipartite graphs as well this bipartite graph for example we could write like this K subscript 3 1 or K subscript 1 3 remember that K subscript n denotes a complete graph on n vertices so the K tells us it's going to be some sort of complete graph and then the 3 comma 1 tells us that it is in fact a complete bipartite graph where one part tight set will have three vertices and the other part tight set will have one vertex and of course this tells us the same thing complete bipartite graph one part tight set has one vertex and the other part tight set has three vertices now I've already drawn a very beautiful k32 graph for us to look at so let's take a look at that this is a complete bipartite graph with partite sets of cardinality three and two as the subscript tells us three and to see how each vertex and this part tight set has degree 3 they're each adjacent to the 3 vertices in the other part tight set whereas each vertex in this part tight set has degree 2 they're each adjacent to the two other vertices in the other part I set and so that's what a complete bipartite graph is it is a bipartite graph with every possible edge so every pair of vertices that are in different part I'd sets must be joined by an edge that is a complete bipartite graph then I suppose one question I could leave you with consider a complete bipartite graph km n so one part I set has n vertices and the other has n vertices what will the size of this graph be as in how many edges does it have pretty simple question and answer just a nice little question to get you thinking about complete bipartite graphs and if you know what Hamiltonian graphs are another question would be which complete bipartite graphs are Hamiltonian I already did a lesson on that so I'll leave a link to that lesson in the description in any event I hope this video helped you understand what complete bipartite graphs are I want to give a big thanks to Baron of lols who supports wrath of math on patreon if you're interested in helping out wrath of math you can go to the patreon page I'll leave a link in the description as well as in the end cards you can pledge basically whatever you want a dollar a month five dollars a month anything at all I greatly appreciate all of your support the likes the comments the shares to help me keep bringing you new lessons every other day thanks a lot and be sure to subscribe for the swankiest math lessons on the internet and a big thanks to valo who upon my request kindly gave me permission to use his music in my math lessons linked to his music in the description [Music] [Music]