24.1.10. Complete Bipartite Graph

Now let us define next what we call as a complete bipartite graph? So, it is a special type of bipartite graph. So, first of all it is a bipartite graph namely it should be possible to come up with a partition of the vertex set, and that partition should have a special property. You take any edge in the graph one of its end point should be in V other end point should be in V that comes from the definition of the bipartite graph.

A complete bipartite graph is a specific kind of bipartite graph that has the property that every vertex in one set is connected to every vertex in the other set. This means that if we split the graph's set of vertices into two parts, every possible edge between these parts exists in the graph. For example, if the vertex sets are V1 and V2, then for every v1 in V1 and every v2 in V2, there is an edge (v1, v2). This ensures that there is no edge between vertices within the same set, adhering to the bipartite property.

Imagine a classroom scenario where students (V1) are assigned to different projects (V2). Each student has to work on every project, meaning there's a direct connection (edge) between each student and every project. So if we have 3 students and 2 projects, there will be direct working connections between each student and both projects, which exemplifies a complete bipartite graph.

But this implication is now a bi-implication, that means it is the case that you have an edge in the graph between each and every vertex in the set V and the set V. So, if you compare this bi-implication condition with the previous definition, in the previous definition it might be possible that you have some vertices in V and some vertices in V such that between those vertices you do not have an edge in the graph.

The key property of complete bipartite graphs is that not only must they satisfy the conditions of a regular bipartite graph, but they must have an edge connecting every vertex in set V1 with every vertex in set V2. This creates a structure where there are no isolated vertices in either set concerning the other set. In contrast, a regular bipartite graph might not have edges connecting some vertices.

Consider a social event where you have a group of people (V1) and a group of activities (V2). In a complete bipartite graph scenario, every person is required to engage in every activity. So if there are 4 people and 3 activities, every person will participate in all activities, reflecting that every vertex from one set connects to all vertices from the other set.

So, for instance if I take this graph then this is a bipartite graph but this is not a complete bipartite graph. Why is not a complete bipartite graph? Because if I say for instance, you take this vertex it will be in one of the subsets given by your partition. And you take this blue colored node this will be in the other subset in your partition, but you do not have an edge between these two vertices in the graph.

In this example, we are looking at a graph that fulfills the conditions to be a bipartite graph but falls short of being a complete bipartite graph. For it to be complete, every vertex must connect to every vertex in the opposite set. Here, there exists at least one pair of vertices, one from each set, that do not share an edge, which violates the completeness requirement.

Think of a sports team selection where you have players (V1) and positions (V2). If each position doesn't have an assigned player, such as a goalkeeper being without an associated player, this demonstrates a bipartite selection without a complete connection. However, if every position had a player assigned, it would resemble a complete bipartite assignment.

So, that is why this graph is not a bipartite graph but this graph is a bipartite graph because you can put the vertices u1, u2, u3 in one subset and you can put the other vertices namely v1, v2, v3, v4 in the other subset namely V2.

When denoting complete bipartite graphs, we use the notation K_{m,n}, where m and n represent the sizes of the two sets of vertices. This notation helps to quickly express how many vertices are present in each set.

If we have a project that requires teams from multiple departments (let's say Marketing and Development), you might name this complete bipartite graph K_{3,4} if there are 3 teams in Marketing and 4 in Development. Every Marketing team interacts directly with every Development team, creating a rich network of collaboration.

--