Hubbry Logo
Bipartite graphBipartite graphMain
Open search
Bipartite graph
Community hub
Bipartite graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Bipartite graph
Bipartite graph
Bipartite graph
View on Wikipedia
from Wikipedia
Example of a bipartite graph without cycles
A complete bipartite graph with m = 5 and n = 3
The Heawood graph is bipartite.

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]

The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.[3][4] In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

One often writes to denote a bipartite graph whose partition has the parts and , with denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;[5] in this case, the notation is helpful in specifying one particular bipartition that may be of importance in an application. If , that is, if the two subsets have equal cardinality, then is called a balanced bipartite graph.[3] If all vertices on the same side of the bipartition have the same degree, then is called biregular.

Examples

[edit]

When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis.[6]

Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.[7]

More abstract examples include the following:

  • Every tree is bipartite.[4]
  • Cycle graphs with an even number of vertices are bipartite.[4]
  • Every planar graph whose faces all have even length is bipartite.[8] Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.[9]
  • The complete bipartite graph on m and n vertices, denoted by Kn,m is the bipartite graph , where U and V are disjoint sets of size m and n, respectively, and E connects every vertex in U with all vertices in V. It follows that Km,n has mn edges.[10] Closely related to the complete bipartite graphs are the crown graphs, formed from complete bipartite graphs by removing the edges of a perfect matching.[11]
  • Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.[12]

Properties

[edit]

Characterization

[edit]

Bipartite graphs may be characterized in several different ways:

  • An undirected graph is bipartite if and only if it does not contain an odd cycle.[13][14]
  • A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).[3]
  • A graph is bipartite if and only if every edge belongs to an odd number of bonds, minimal subsets of edges whose removal increases the number of components of the graph.[15]
  • A graph is bipartite if and only if the spectrum of the graph is symmetric.[16]

Kőnig's theorem and perfect graphs

[edit]

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[17][18] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.[19] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.

Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.[20] Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree.

According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.[21] It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.[22]

Degree

[edit]

For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted . The degree sum formula for a bipartite graph states that[23]

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts and . For example, the complete bipartite graph K3,5 has degree sequence . Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

Relation to hypergraphs and directed graphs

[edit]

The biadjacency matrix of a bipartite graph is a (0,1) matrix of size that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.[24] Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph may be used to model a hypergraph in which U is the set of vertices of the hypergraph, V is the set of hyperedges, and E contains an edge from a hypergraph vertex v to a hypergraph edge e exactly when v is one of the endpoints of e. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.[25]

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with n vertices can be any (0,1) matrix of size , which can then be reinterpreted as the adjacency matrix of a bipartite graph with n vertices on each side of its bipartition.[26] In this construction, the bipartite graph is the bipartite double cover of the directed graph.

Algorithms

[edit]

Testing bipartiteness

[edit]

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search (DFS). The main idea is to assign to each vertex the color that differs from the color of its parent in the DFS forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a DFS forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.[27]

Alternatively, a similar procedure may be used with breadth-first search in place of DFS. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.[28]

For the intersection graphs of line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time , even though the graph itself may have up to edges.[29]

Odd cycle transversal

[edit]
Main article: Odd cycle transversal
A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.

Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.[30] The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.[31] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.

The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also fixed-parameter tractable, and can be solved in time ,[32] where k is the number of edges to delete and m is the number of edges in the input graph.

Matching

[edit]
Main article: Matching (graph theory)

A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.[33] In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[34] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[35] work correctly only on bipartite inputs.

As a simple example, suppose that a set of people are all seeking jobs from among a set of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph where an edge connects each job-seeker with each suitable job.[36] A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.[37]

The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.[38]

Additional applications

[edit]

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. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.[39] A factor graph is a closely related belief network used for probabilistic decoding of LDPC and turbo codes.[40]

In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled 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.[41]

In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their girth must be six or more.[42]

See also

[edit]
  • Bipartite dimension, the minimum number of complete bipartite graphs whose union is the given graph
  • Bipartite double cover, a way of transforming any graph into a bipartite graph by doubling its vertices
  • Bipartite hypergraph, a generalization of bipartiteness to hypergraphs.
  • Bipartite matroid, a class of matroids that includes the graphic matroids of bipartite graphs
  • Bipartite network projection, a weighting technique for compressing information about bipartite networks
  • Convex bipartite graph, a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
  • Multipartite graph, a generalization of bipartite graphs to more than two subsets of vertices
  • Parity graph, a generalization of bipartite graphs in which every two induced paths between the same two points have the same parity
  • Quasi-bipartite graph, a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphs
  • Split graph, a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a clique
  • Zarankiewicz problem on the maximum number of edges in a bipartite graph with forbidden subgraphs

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Bipartite graph

View on Grokipedia
from Grokipedia
In , a bipartite graph is an undirected graph whose vertices can be partitioned into two such that no two graph vertices in the same set are adjacent, meaning every edge connects a vertex in one set to a vertex in the other. This partition, often denoted as sets UU and VV, ensures that the graph has no edges within UU or within VV, making it a fundamental structure for modeling binary relations. Bipartite graphs exhibit several key properties that distinguish them from general graphs, including the absence of odd-length cycles, as any cycle must alternate between the two sets and thus have even length. Equivalently, a graph is bipartite if and only if it is 2-colorable, where vertices can be with two colors such that no adjacent vertices share the same color, reflecting the partition into independent sets. These properties imply that bipartite graphs have chromatic number at most 2 and are useful for algorithmic efficiency in problems like and . Beyond their structural characteristics, bipartite graphs find wide applications in optimization and modeling real-world scenarios involving two distinct categories. For instance, they model assignment problems such as matching jobs to workers or students to courses, where one set represents candidates and the other resources. Key theorems like provide conditions for the existence of perfect matchings in bipartite graphs, enabling solutions to stable matching problems like the stable marriage and hospital-residents dilemma. Additionally, bipartite graphs underpin network flow algorithms for minimum and maximum matching, with applications in scheduling, , and .

Fundamentals

Definition

A bipartite graph is an undirected graph G=(V,E)G = (V, E) whose vertex set VV can be partitioned into two disjoint independent sets UU and WW such that U∩W=∅U \cap W = \emptyset, U∪W=VU \cup W = V, and every edge in EE connects a vertex in UU to a vertex in WW. This partition ensures that no edges exist within UU or within WW, resulting in a two-part structure where interactions occur exclusively between the sets. The Km,nK_{m,n} denotes the bipartite graph with partition sets of sizes m=∣U∣m = |U| and n=∣W∣n = |W|, where every vertex in UU is adjacent to every vertex in WW, yielding m×nm \times n edges. This notation highlights the balanced or imbalanced nature of the partitions and serves as a foundational example for studying bipartite structures. The term "bipartite" for such graphs was introduced by Dénes Kőnig in his 1931 paper "Graphok és matrixok," in the context of graph colorings and matrix theory.

Characterization

A bipartite graph is equivalently characterized as a graph that admits a proper 2-coloring of its vertices, meaning the vertices can be colored using exactly two colors such that no two adjacent vertices share the same color. This equivalence holds because the two color classes naturally form the independent sets in the bipartition. To verify 2-colorability and thus bipartiteness, a proof sketch involves applying a graph traversal algorithm such as breadth-first search (BFS) or depth-first search (DFS) from each connected component. Begin by assigning one color to a starting vertex and alternating colors for its neighbors; a conflict arises if an adjacent vertex is assigned the same color, indicating non-bipartiteness. If no conflicts occur across all components, the graph is 2-colorable. Another fundamental characterization states that a graph is bipartite if and only if it contains no odd-length cycles. In a bipartite graph, every cycle must alternate between the two partitions, resulting in even length; conversely, the presence of an odd cycle implies non-bipartiteness, as it would force at least one edge to connect two vertices in the same partition during any attempted 2-coloring, leading to a monochromatic edge by contradiction. This parity condition provides a cycle-based test for bipartiteness distinct from but equivalent to the coloring approach. From an extremal perspective, the Zarankiewicz problem characterizes the maximum number of edges in an m-by-n bipartite graph without a complete bipartite subgraph K_{s,t}, offering bounds on dense bipartite structures free of forbidden subgraphs.

Examples

Illustrative Graphs

A fundamental class of bipartite graphs is the complete bipartite graphs Km,nK_{m,n}, consisting of two disjoint vertex sets UU and VV with ∣U∣=m|U| = m and ∣V∣=n|V| = n, where every vertex in UU connects to every vertex in VV, but no edges exist within UU or VV. A specific instance is the star graph K1,nK_{1,n}, featuring a single central vertex adjacent to nn isolated leaves, illustrating a tree structure with all edges crossing the partitions. Even-length cycles, denoted C2kC_{2k} for integer k≥2k \geq 2, form another basic example; their vertices alternate between two partitions as one traverses the cycle, ensuring no intra-partition edges. Paths of arbitrary length are also bipartite, as they lack cycles and can be colored alternately along the chain. More generally, all trees—acyclic connected graphs—are bipartite, with partitions determined by levels from any root or by parity of distances. To contrast, non-bipartite graphs include odd-length cycles C2k+1C_{2k+1}, such as the C3C_3, which cannot be partitioned without intra-set edges due to the odd cycle. Complete graphs KnK_n for n≥3n \geq 3 similarly fail bipartiteness, as they contain triangles and other odd cycles among their fully connected vertices. The K3,3K_{3,3} exemplifies edge distribution: visualize two parallel rows of three vertices each (partitions U={u1,u2,u3}U = \{u_1, u_2, u_3\} and V={v1,v2,v3}V = \{v_1, v_2, v_3\}), with nine edges forming a dense grid where each uiu_i links to all vjv_j, but none within rows, highlighting the exhaustive cross-connections. Another illustrative construction is the bipartite double cover of a graph GG, formed by duplicating each vertex vv into v1v_1 and v2v_2, then replacing each original edge uvuv with edges u1v2u_1 v_2 and u2v1u_2 v_1; the resulting graph is always bipartite, with partitions separating the subscript-1 and subscript-2 copies, and edges solely between them. The enumeration of bipartite graphs underscores their restriction compared to general graphs: while the total number of simple labeled graphs on nn vertices is 2(n2)2^{\binom{n}{2}}, the count of unlabeled bipartite graphs is smaller, yielding 1, 2, 3, 7, 13, 35, and 88 for n=1n = 1 to 77, reflecting the limit to edges between partitions. For labeled cases, the total arises from summing over partition sizes, giving ∑k=0n(nk)2k(n−k)\sum_{k=0}^{n} \binom{n}{k} 2^{k(n-k)}.

Real-World Models

Bipartite graphs serve as effective models for incidence structures in geometry, where one partition represents points and the other represents lines, with edges indicating incidence relations between them. For instance, in projective geometry, the point-line incidence graph captures the relationships in finite geometries, enabling the study of combinatorial properties such as the number of incidences and extremal bounds. This modeling approach facilitates analysis in discrete geometry, where the bipartite structure highlights the absence of edges within point or line sets, reflecting the inherent separation of these geometric elements. In recommendation systems, bipartite graphs model user-item interactions by partitioning users into one set and items (such as products or media) into another, with edges representing interactions like ratings or purchases. This structure underpins techniques, where the graph encodes sparse interaction data to infer preferences and generate suggestions. Seminal work in this area leverages the bipartite framework to address scalability in large-scale systems, such as those used by platforms. Social networks often employ to represent collaborations, particularly in the Hollywood actor-movie graph, where one partition consists of actors and the other of movies, with edges connecting actors to films they have appeared in. This model reveals power-law degree distributions, with actors having varying numbers of credits and movies featuring multiple casts, leading to clustering coefficients around 0.785 and average path lengths of about 3.6 in datasets from the Internet Movie Database. Such representations highlight community structures and influence propagation in without assuming direct connections within actor or movie sets. In biological networks, bipartite graphs model interactions between different types, such as compounds and proteins, where one partition holds compounds (e.g., drugs) and the other proteins (e.g., targets), with edges denoting binding or functional associations. This approach is common in and , allowing the integration of heterogeneous data like compound-protein interaction networks to predict novel associations. For example, in compound-protein prediction tasks, the bipartite structure supports models that learn embeddings from these interactions across diverse biological entities. Transportation and systems utilize bipartite graphs to model supply-demand matching, with one partition representing supply nodes (e.g., warehouses or sources) and the other demand nodes (e.g., customers or destinations), where edges incorporate costs or capacities for potential shipments. This formulation transforms the transportation problem into a network flow optimization setup, enabling efficient allocation in scenarios like freight or market choice decisions. In such models, the bipartite nature ensures that flows occur only between supply and demand, reflecting real-world constraints in planning.

Properties

Structural Properties

A bipartite graph G=(V,E)G = (V, E) with bipartition (U,V)(U, V), where UU and VV partition the vertex set and all edges connect vertices between UU and VV, has the property that both UU and VV are independent sets—no edges exist within either set. This structural feature ensures the absence of edges connecting vertices in the same partition, distinguishing bipartite graphs from those with intra-partition connections. As a consequence of lacking odd-length cycles, bipartite graphs are inherently triangle-free, since a triangle constitutes a cycle of three. This triangle-free nature extends to the prohibition of any odd cycles, reinforcing the independence of the partitions and limiting possible subgraph structures. Regarding planarity, not all bipartite graphs are planar; for instance, the complete bipartite graph K3,3K_{3,3} cannot be embedded in the plane without edge crossings. Kuratowski's theorem characterizes planar graphs as those without K5K_5 or K3,3K_{3,3} as minors, and since K3,3K_{3,3} is bipartite, any bipartite graph containing a K3,3K_{3,3} minor is non-planar. The complement of a bipartite graph exhibits a distinct clique structure: with partitions UU and VV, the complement forms complete cliques on UU and on VV, augmented by edges between UU and VV precisely where the original graph lacked them. This results in a cobipartite graph, where the vertex set partitions into two cliques, highlighting the duality between bipartite and clique-based structures. Spectral properties of bipartite graphs arise from the block structure of their , which, when vertices are ordered by partitions, takes the form (0BBT0),\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}, where BB is the biadjacency matrix. A hallmark feature is the of the about zero: the eigenvalues are symmetric, meaning if λ\lambda is an eigenvalue with multiplicity mm, then −λ-\lambda is also an eigenvalue with multiplicity mm. This property reflects the balanced, two-part nature of the graph without delving into explicit computations.

König's Theorem

König's theorem, proved by Dénes König in 1931, states that in any bipartite graph, the cardinality of a maximum matching equals the cardinality of a minimum vertex cover. This duality highlights a fundamental optimization property unique to bipartite graphs, where the minimum number of vertices needed to cover all edges matches the maximum number of pairwise disjoint edges. A common proof outline begins with a maximum matching M and constructs a vertex cover C of the same size by including all unsaturated vertices in one partite set and the endpoints in the other set reached via alternating paths starting from unsaturated vertices. These alternating paths, which alternate between edges in M and not in M, cannot form augmenting cycles due to the bipartiteness, ensuring no larger matching exists and that C covers all edges. One direction of the proof—that the vertex cover size is at most the matching size—relies on Hall's marriage theorem, which ensures matchings exist when neighborhood sizes satisfy certain expansion conditions, allowing the inductive construction of covers. In contrast, non-bipartite graphs satisfy only the inequality that the maximum matching size is at most the minimum vertex cover size, as captured by the Gallai identities, which relate these quantities to the independence number and edge cover size without equality in general. The theorem's implications enable efficient computation of minimum vertex covers in bipartite graphs by reducing the problem to finding a maximum matching, solvable in time. It also connects to total coloring, where the edge-coloring version of König's theorem (stating that the chromatic index equals the maximum degree Δ) allows vertices to be colored with an additional color beyond the Δ edge colors, yielding a total chromatic number of Δ + 1 for bipartite graphs. An important extension addresses edge covers: in any graph without isolated vertices, the size of a minimum edge cover equals the number of vertices minus the size of a maximum matching, a relation that in bipartite graphs follows directly from König's theorem via the Gallai identities.

Degree Sequences

In bipartite graphs, the degree sequence is partitioned into two non-increasing sequences of non-negative integers, one for each part of the vertex partition, say d=(d1≥d2≥⋯≥dm)d = (d_1 \geq d_2 \geq \cdots \geq d_m) for the first part and e=(e1≥e2≥⋯≥en)e = (e_1 \geq e_2 \geq \cdots \geq e_n) for the second part. A pair of sequences (d,e)(d, e) is said to be bipartite graphical (or bigraphic) if there exists a simple bipartite graph realizing these degrees. The Gale-Ryser theorem provides the necessary and sufficient conditions for this realization. The theorem states that (d,e)(d, e) is bigraphic if and only if ∑i=1mdi=∑j=1nej\sum_{i=1}^m d_i = \sum_{j=1}^n e_j and the conjugate partition e∗e^* of ee majorizes dd. Here, the conjugate e∗e^* is defined such that ek∗e^*_k is the number of parts in ee that are at least kk, for k=1,2,…,max⁡ejk = 1, 2, \dots, \max e_j. Majorization means that ∑i=1kdi≤∑i=1kei∗\sum_{i=1}^k d_i \leq \sum_{i=1}^k e^*_i for all k=1,…,mk = 1, \dots, m, with equality when k=mk = m. This condition ensures the existence of a (0,1)-matrix with row sums dd and column sums ee, which corresponds directly to the adjacency matrix of the bipartite graph. The theorem was established independently by Gale and by Ryser. For example, consider a kk-regular bipartite graph with equal part sizes m=nm = n. The degree sequences are both (k,k,…,k)(k, k, \dots, k) ( mm times each), and the total edges match as km=knk m = k n. The conjugate of the column sequence is (m,m,…,m)(m, m, \dots, m) ( kk times, padded with zeros), which majorizes the row sequence since both are uniform and sums equal, confirming realizability (e.g., the complete bipartite graph Km,mK_{m,m} achieves this for k=mk = m). In contrast, for general (non-bipartite) graphs, the Erdős–Gállai theorem characterizes a single degree sequence d1≥⋯≥dNd_1 \geq \cdots \geq d_N via ∑i=1kdi≤k(k−1)+∑i=k+1Nmin⁡(di,k)\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^N \min(d_i, k) for k=1,…,Nk = 1, \dots, N, with equality in the total sum; this accounts for potential odd cycles absent in bipartite realizations. The Gale-Ryser theorem extends to applications in generating random bipartite graphs via the , where stubs (half-edges) are paired randomly according to the prescribed degrees dd and ee. For the resulting to admit a simple graph realization, the sequences must satisfy the theorem's conditions; otherwise, multiple edges or loops may occur, and conditioning on simplicity yields a uniform random simple bipartite graph with those degrees. This model is widely used to study properties like connectivity and matching sizes under fixed degree distributions.

Connections to Other Structures

Bipartite graphs are intimately connected to hypergraphs through the concept of incidence graphs. The incidence graph of a hypergraph H=(V,E)H = (V, E) is a bipartite graph with partite sets VV (the vertices of HH) and EE (the hyperedges of HH), where an edge exists between a vertex v∈Vv \in V and a hyperedge e∈Ee \in E if and only if v∈ev \in e. This construction preserves the incidence structure of the hypergraph while embedding it into a bipartite framework. Conversely, every bipartite graph can be interpreted as the incidence graph of a hypergraph, where one partite set represents vertices and the other represents hyperedges; in cases with multiple edges, this corresponds to a multihypergraph. In the context of directed graphs, bipartite graphs admit straightforward acyclic orientations. Specifically, by directing all edges from one partite set to the other, any bipartite graph becomes a (DAG) with no directed cycles, leveraging the absence of odd cycles in the undirected structure. This orientation yields a bipartite DAG, where the two partite sets serve as natural layers. Furthermore, complete bipartite graphs can be oriented to form bipartite tournaments, which are directed graphs without symmetric edges and with specific regularity properties in balanced cases. Bipartite multigraphs extend the simple bipartite graph model by permitting multiple edges between vertices in different partite sets, while weighted bipartite graphs incorporate real-valued weights on edges without altering the underlying bipartition. These variants maintain core bipartite properties, such as the absence of odd cycles, and facilitate modeling scenarios involving capacities or multiplicities. For infinite bipartite graphs, foundational results like König's duality theorem extend to the infinite setting, ensuring the existence of matchings that cover infinite sets under certain conditions. A related highlight is König's lemma, which applies to infinite trees—a special class of bipartite graphs without cycles—stating that every infinite, finitely branching tree contains an infinite path. This underscores the structural parallels between finite and infinite bipartite graphs in combinatorial contexts.

Algorithms

Testing Bipartiteness

Testing bipartiteness of a graph can be accomplished efficiently using algorithms that attempt to 2-color the vertices, leveraging the equivalence between bipartiteness and 2-colorability. The (BFS)-based algorithm begins by selecting an arbitrary uncolored vertex as the source and assigning it color 0. It then explores the graph layer by layer, assigning color 1 to all neighbors of color-0 vertices and color 0 to their neighbors, ensuring adjacent vertices receive opposite colors. During traversal, if an edge connects two vertices of the same color, an odd-length cycle is detected, indicating the graph is not bipartite. This process runs in O(|V| + |E|) time, visiting each vertex and edge exactly once. To handle disconnected graphs, the algorithm iterates over all vertices, initiating a BFS from any uncolored vertex to process each connected component separately. If no color conflicts arise across all components, the graph is bipartite, and the coloring provides the two partitions. A depth-first search (DFS) variant operates recursively or via a stack, starting from a source vertex colored 0 and coloring each subsequent vertex opposite to its parent. Upon encountering a back edge or adjacent edge to a visited vertex, it verifies that the colors differ; a match signals a non-bipartite graph. Like BFS, this achieves O(|V| + |E|) time complexity and extends naturally to disconnected graphs by traversing unvisited components. Union-find structures can be adapted for this task by maintaining for color classes within components, unioning vertices with their opposites across edges and detecting conflicts via path compression and rank heuristics, though traversal methods remain more conventional for static graphs. The correctness of these approaches follows from the 2-colorability : successful coloring without conflicts confirms bipartiteness and yields the partition sets.

Odd Cycle Transversal

An odd cycle transversal (OCT) of an undirected graph G=(V,E)G = (V, E) is a subset S⊆VS \subseteq V such that the graph G−SG - S induced by V∖SV \setminus S contains no odd-length cycles and is thus bipartite. The minimum odd cycle transversal problem asks for the smallest such SS, and it is a graph editing problem aimed at achieving bipartiteness through vertex deletions. The decision version of minimum OCT, parameterized by the solution size k=∣S∣k = |S|, is NP-complete in general graphs. However, the problem is fixed-parameter tractable (FPT), admitting algorithms running in time f(k)⋅nO(1)f(k) \cdot n^{O(1)} for some ff, where n=∣V∣n = |V|. The seminal FPT algorithm, introduced by Reed, Smith, and Vetta in 2004, employs iterative compression to solve disjoint instances of OCT and achieves a runtime of O(2kn3)O(2^k n^3). Subsequent improvements have refined this to single-exponential time, such as O(2.3146k)O(2.3146^k) using techniques like measure-and-conquer analysis. If the input graph GG is already bipartite, the minimum OCT is trivially the empty set, as no odd cycles exist to hit; this case reduces to standard bipartiteness testing via BFS or DFS in linear time. For non-bipartite graphs, algorithms for OCT often adapt methods from the (FVS) problem, which hits all cycles, by focusing exclusively on odd cycles through branching or dynamic programming on conflict graphs derived from potential bipartitions. The minimum OCT problem admits an integer linear programming (ILP) formulation as follows: introduce a binary variable xv∈{0,1}x_v \in \{0,1\} for each vertex v∈Vv \in V indicating whether vv is selected in the transversal; minimize ∑v∈Vxv\sum_{v \in V} x_v subject to ∑v∈Cxv≥1\sum_{v \in C} x_v \geq 1 for every odd cycle CC in GG. This ILP has exponentially many constraints due to the potential number of odd cycles, rendering it impractical for direct solving without enumeration; however, in parameterized settings, it can be addressed via separation oracles that efficiently find violated constraints using flow-based methods or randomized techniques. Reductions to ILP solvers are common in FPT algorithms, often via relaxations solved to optimality with rounding or branch-and-bound tailored to the parameter kk. Regarding 2-SAT reductions, OCT is FPT-equivalent to Almost 2-SAT (where at most kk clauses are violated in a 2-CNF formula), allowing bidirectional parameterized reductions that transform instances while preserving the parameter size. In the context of parameterized complexity, kernelization techniques for OCT reduce the input instance to one whose size is bounded by a in kk, enabling faster resolution. A notable approach uses linear matroids to encode odd cycle hitting constraints, yielding a kernel with O(k2)O(k^2) vertices through a series of min-cut computations interpreted matroidally. More recent developments include randomized kernels of size O(k2log⁡k)O(k^2 \log k) via iterative compression simulations, and deterministic ones for restricted graph classes like planar graphs. These kernels facilitate preprocessing in FPT solvers and highlight OCT's role in advancing kernelization theory.

Matching Algorithms

In bipartite graphs, finding a maximum matching—a largest set of edges with no shared vertices—is a fundamental problem with applications in and scheduling. A key theoretical foundation is , which provides a necessary and sufficient condition for the existence of a (one that covers all vertices in both partitions). For a bipartite graph G=(U∪V,E)G = (U \cup V, E) with ∣U∣=∣V∣|U| = |V|, there exists a if and only if for every subset S⊆US \subseteq U, the neighborhood N(S)⊆VN(S) \subseteq V satisfies ∣N(S)∣≥∣S∣|N(S)| \geq |S|; this condition symmetrically holds when swapping UU and VV. The theorem, proved using combinatorial arguments on systems of distinct representatives, ensures no "bottleneck" subsets obstruct a complete matching. Algorithms for computing maximum matchings in bipartite graphs typically rely on finding and augmenting along paths that increase the matching size, starting from an empty matching and repeating until no such path exists. The Hungarian algorithm, developed by Harold W. Kuhn in 1955, solves the assignment problem (a weighted variant) but adapts to unweighted maximum cardinality matching by treating all edges equally. It proceeds by iteratively identifying augmenting paths using a step-by-step process: maintain dual variables (potentials) for vertices to ensure reduced costs are non-negative, then use breadth-first search (BFS) or depth-first search (DFS) in the equality subgraph to find shortest augmenting paths, updating the matching and adjusting potentials after each augmentation. This yields a time complexity of O(∣V∣3)O(|V|^3) for graphs with ∣V∣|V| vertices, making it efficient for dense graphs up to moderate sizes. For improved efficiency on sparse graphs, the Hopcroft-Karp algorithm, introduced by John E. Hopcroft and Richard M. Karp in 1973, achieves O(∣E∣∣V∣)O(|E| \sqrt{|V|})
Add your contribution
Related Hubs
User Avatar
No comments yet.