24.1.9. Bipartite Graphs

Now let us next define what we call as Bipartite graphs. So, if you are given a simple graph, then the graph is called bipartite, if we can find out two vertex sets V₁ and V₂ such that the following whole the vertex sets V₁ and V₂ should constitute a partition of your vertex set. That means V = V₁ ∪ V₂ and V₁ ∩ V₂ = ∅.

A bipartite graph is defined by two sets of vertices (nodes) such that all edges in the graph connect vertices from one set to the other, never within the same set. This means you can think of the two sets as two different groups where no two individuals from the same group are directly connected by an edge. For a graph to be bipartite, it must fulfill two conditions: the vertex set must be entirely divided into two distinct sets with no intersection, and every edge must connect a vertex from one set to a vertex from the other set.

Imagine a school where there are two groups of students: the students who play soccer and the students who play basketball. In a bipartite graph, every player can only interact with a player from the other sport for organizing a match, not with another player from their own sport. If soccer players can only connect with basketball players, it forms a bipartite relationship.

And the second property that I need from this partition V₁ and V₂ is the following. I need the following: you take any edge E in the graph whose endpoints are v₁ and v₂, then one of the endpoints should be in one of the subsets and the other endpoint should be in the other subset.

This property emphasizes that for every edge in the bipartite graph, its two endpoints must come from the two distinct sets. This prevents any edge from connecting two vertices within the same subset, maintaining the separation required in bipartite graphs. If any edge were to connect two vertices within the same set, it would contradict the definition and make the graph not bipartite.

Continuing with the sports analogy, suppose each soccer player can only collaborate with a basketball player to create a team for a school event. If a soccer player tried to form a partnership with another soccer player, it would not be allowed in this scenario. This showcases how edges must always connect different groups, aligning with the bipartite property.

So, for instance, if I take this graph then, this graph is not a bipartite graph because I cannot find the required V₁ set and V₂ set. This is because if I focus on the specific portion of the graph, namely this portion is the triangle graph.

The example described shows that a specific graph (in this case, a triangle graph) does not meet the requirements to be considered bipartite. In a triangle graph, each vertex connects to each other, meaning that you cannot separate them into two groups without having edges between vertices in the same group. Thus, it fails to fulfill the bipartite conditions, illustrating how certain arrangements of vertices and edges cannot be bipartite.

Think of a social circle consisting of three friends where each friend knows the other two. If you attempt to divide them into two groups (say, one group includes Friend A and B, and the other includes Friend C), it would be impossible to satisfy the bipartite condition since each friend can communicate with each other. They represent a scenario where there is an absence of a bipartite structure.

Now let us define next what we call as a complete bipartite graph. So, it is a special type of bipartite graph where you take any edge in the graph one of its endpoints should be in V₁ and the other endpoint should be in V₂, but this implication now is a bi-implication.

A complete bipartite graph not only requires that vertices in one set connect to vertices in the other but also that every possible connection exists between these two groups. This means every vertex in the first set is connected to every vertex in the second set. In terms of notation, complete bipartite graphs are often denoted as K(m, n), where m and n represent the number of vertices in each of the two sets.

Consider a dating event where all individuals from one group (say, 5 people) are introduced to all individuals from another group (say, 4 people). In a complete bipartite scenario, every person from Group One will get to meet every person from Group Two, establishing a perfect match connection, demonstrating the interaction between the two groups.

--