In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets U and V such that no edge has both end-points in the same set. Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... This article just presents the basic definitions. ... In mathematics, two sets are said to be disjoint if they have no element in common. ... This article just presents the basic definitions. ...

Intuitive definition

The best way to think of a bipartite graph is one whose nodes can be colored red and blue such that no edge exists between like colors. For example, this cannot be done with a fully connected graph with 3 vertices (a triangle). (If the first node is colored red and the second one is colored blue, what happens to the third?) A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...

Mathematical definition

A simple undirected graph is called bipartite if there exists a partition of the vertex set so that both V₁ and V₂ are independent sets. One often writes to denote a bipartite graph whose partition has the parts V₁ and V₂. If | V₁ | = | V₂ | , that is, if the number of elements in V₁ is equal to the number of elements in V₂, then G is called a balanced bipartite graph. This article just presents the basic definitions. ... This article just presents the basic definitions. ... A partition of U into 6 blocks: a Venn diagram representation. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ...

Applications

Bipartite graphs are useful for modelling matching problems. An example of bipartite graph is a job matching problem. Suppose we have a set of people P and a set of jobs J, with not all people suitable for all jobs. We can model this as a graph with P + J the set of vertices. If a person p_i is suitable for a certain job j_i there is an edge between p_i and j_i in the graph. The marriage theorem provides a characterization of bipartite graphs which allow perfect matchings. This article is about mathematical matchings. ... In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets. ... In mathematics, a perfect matching for a graph is a matching (a subset of edges without common vertices) which touches all vertices exactly once. ...

Bipartite graphs are extensively used in modern Coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. ... A factor graph is an -bipartite graph where is a set of variables and is a set of factors. ... A Tanner graph is a bipartite graph used to specify constraints or equations which specify error correcting codes. ...

In computer science, a Petri net is a mathematical modelling tool used in analysis and simulations of concurrent systems. A system is modelled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system. A Petri net is a mathematical representation of discrete distributed systems. ...

Examples

• Every tree is bipartite.
• Cycle graphs with an even number of vertices are bipartite.

A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...

Properties

• A graph is bipartite if and only if it does not contain an odd cycle.
• The size of minimum vertex cover is equal to the size of the maximum matching (König's theorem).
• The size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
• For a connected bipartite graph the size of the minimum edge cover is equal to the size of the maximum independent set.
• For a connected bipartite graph the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
• A graph is bipartite if and only if it is two colorable, (i.e. its chromatic number is 2).
• Every bipartite graph is perfect.

It has been suggested that this article or section be merged with Logical biconditional. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... This article is about mathematical matchings. ... An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... This article is about mathematical matchings. ... In mathematics and computer science, graph theory studies the properties of graphs. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... In mathematics and computer science, graph theory studies the properties of graphs. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... A 3_coloring suits this graph, but fewer colors would result in adjacent verticies of the same color. ... In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ...

See also

• Complete bipartite graph
• Dulmage-Mendelsohn Decomposition
• Levi graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ... In Graph theory, The Dulmage-Mendelson decomposition is a method used to create an maximal matching on a bipartite graph. ... Levi graph or incidence graph is a bipartite graph associated with an incidence structure. ...

External links

• Information System on Graph Class Inclusions: bipartite graph

• Weisstein, Eric W., Bipartite Graph at MathWorld.