Bipartite graph

You can group things into two sets.

Each part has its own color. One part is red. The other part is blue. Red dots only touch blue dots.

This is like a game of colors. If you see a triangle, it is not a bipartite graph. A triangle has three dots. You cannot color three dots with only two colors. But a square works well. You can color it with red and blue. Even trees follow this rule. This helps us see how things connect.

Imagine you have two groups of dots.

In a bipartite graph, you can split all dots into two sets. We call these sets the parts of the graph. Every line must connect a dot from one part to a dot in the other part. Lines never connect two dots that are in the same set.

You can think of this like a coloring game. If you color one set blue and the other red, every line will touch two different colors.

A triangle is not a bipartite graph. This is because a triangle has an odd cycle. An odd cycle is a loop with an odd number of dots. You cannot color a triangle with just two colors.

These graphs help us model real life. For example, you can map football players to their clubs. One set is the players. The other set is the clubs. A line shows which player played for which club.

You can also find these in math trees. Every tree is a bipartite graph.

A bipartite graph is a special way to organize dots and lines. In math, we call these dots vertices and the lines edges. To be bipartite, you must be able to split all the vertices into two separate groups. We call these groups the parts of the graph. Every single edge must connect a dot from the first group to a dot in the second group. No edge is allowed to connect two dots that are in the same group.

You can also think of this using colors. Imagine you have two colors, like red and blue. If a graph is bipartite, you can color every dot so that no two dots of the same color touch each other. This is called a two-coloring. A triangle is not bipartite because it has an odd cycle. An odd cycle is a loop with an odd number of vertices. In a triangle, the third dot would always touch a dot of the same color.

Many mathematicians have studied these patterns over many years. A man named Dénes Kőnig wrote a paper in 1916 about these graphs. He showed that a graph is bipartite if it has no odd cycles. This is a very important rule in graph theory. Another famous idea is the two color theorem. Some people link this to a paper from 1879 by Alfred Kempe. He was working on a different puzzle called the four color theorem.

There are many different types of these graphs. A complete bipartite graph is one where every dot in the first group connects to every dot in the second group. We use labels like $K_{m,n}$ to describe them. If the two groups have the same number of dots, we call it a balanced bipartite graph. A special version is called a biregular graph. In these graphs, every dot on the same side has the same number of connections.

Bipartite graphs are very useful for solving real problems. You can use them to show how football players relate to their clubs. One group is the players and the other group is the clubs. You can also use them for railway optimization. This helps find the smallest number of stations to cover all train stops. Even simple shapes like trees are always bipartite graphs.

{ "text": "In the mathematical field of graph theory, a bipartite graph is a specific way to organize vertices and edges. A bipartite graph, also called a bigraph, is defined by its ability to be divided into two distinct sets. These sets, known as the parts of the graph, are disjoint and independent. This means that every single edge in the graph must connect a vertex from the first set to a vertex in the second set. No edge is permitted to connect two vertices that belong to the same part.

\n\nThis structure can be understood through the concept of graph coloring. A graph is bipartite if it is 2-colorable, meaning its chromatic number is two or less. If you color all nodes in one set blue and all nodes in the other set red, every edge will connect endpoints of different colors. This is a requirement of the graph coloring problem. In contrast, a non-bipartite graph like a triangle makes this impossible. If you color one node blue and another red, the third vertex in a triangle connects to both colors. Therefore, it cannot be assigned a color without violating the rule.

\n\nA fundamental way to identify these graphs is by looking for cycles. An undirected graph is bipartite if and only if it does not contain any odd-length cycles. This characterization is often attributed to a 1916 paper by Dénes Kőnig. For infinite graphs, however, proving this result requires the axiom of choice. Another way to define them is through bonds. A graph is bipartite if every edge belongs to an odd number of bonds, which are minimal subsets of edges whose removal increases the number of components. Additionally, the spectrum of a bipartite graph is always symmetric.\n\nThere are several specialized types of bipartite graphs. A complete bipartite graph, denoted as $K_{m,n}$, occurs when every vertex in a set of size $m$ connects to every vertex in a set of size $n$. Such a graph contains exactly $m \times n$ edges.

If the two subsets have equal cardinality, the graph is called a balanced bipartite graph. If all vertices on one side of the partition have the same degree, the graph is called biregular. Other examples include crown graphs, which are formed by removing a perfect matching from complete bipartite graphs. Hypercube graphs, partial cubes, and median graphs also fall into the bipartite category.\n\nBipartite graphs appear frequently when modeling relations between two different classes of objects. For example, an affiliation network can map football players to their clubs. In this model, an edge exists only if a player has played for a specific club. Another complex application is the railway optimization problem. This is an NP-complete problem involving train schedules and stops. It can be modeled as a dominating set problem in a bipartite graph. In this version, one set of vertices represents trains and the other represents stations. An edge connects a train to a station if that train stops there.\n\nMathematical theorems provide deep insights into the properties of these graphs. Kőnig's theorem states that in bipartite graphs, the size of a minimum vertex cover equals the size of a maximum matching. An equivalent form says the size of the maximum independent set plus the maximum matching equals the total number of vertices. Bipartite graphs are also part of the class of perfect graphs. This perfection is easy to see because their chromatic number and maximum clique size are both two. The strong perfect graph theorem notes that bipartite graphs are characterized by having no odd cycles as subgraphs.\n\nResearchers use various algorithms to test for bipartiteness efficiently. Using a depth-first search (DFS) or a breadth-first search (BFS), one can test a graph in linear time. The process involves assigning colors to vertices in a way that differs from their parent in a search forest. If the algorithm finds an edge connecting two vertices of the same color, it has discovered an odd cycle. This proves the graph is not bipartite.

For intersection graphs of simple shapes in a plane, testing can be done in $O(m \sqrt{n})$ time. This allows mathematicians to quickly categorize complex networks and solve optimization problems.", "media": [ "File:Biclique K 3 5 bicolor.svg", "File:Heawood graph bipartite (bicolor).svg", "File:Odd Cycle Transversal of size 2.png" ] }