Can a bipartite graph contain cycles?

Yes, but an undirected bipartite graph cannot contain an odd cycle.

Can it contain isolated vertices?

Yes. They have no edges violating the partition.

Is every tree bipartite?

Yes. Alternating colors along its edges produces a valid partition because a tree has no cycles.

AI Glossary / Graphs and symbolic AI / Beginner

Bipartite

Definition

A bipartite graph is a graph whose vertices can be divided into two disjoint sets so that every edge joins a vertex in one set to a vertex in the other. No edge connects two vertices within the same set.

What it means

Many relationship datasets naturally involve two roles: people and projects, customers and products, or workers and tasks. A bipartite graph preserves those roles. An edge can mean that a person belongs to a project, a customer purchased a product or a worker is qualified for a task.

Bipartite describes structure, not whether the two sides have equal sizes or whether every possible cross-set connection exists. A complete bipartite graph is the special case containing all possible edges between its two sets.

The graph need not be connected. An isolated vertex can be placed on either side unless external meaning fixes its role. For disconnected graphs, the structural partition is not necessarily uniquely determined; domain labels may be needed to preserve the intended interpretation.

A matching is a separate concept: it selects edges that do not share endpoints. A bipartite dataset can have many edges per vertex even when a later assignment problem seeks a one-to-one matching.

How it works

A standard test attempts to color each connected component with two colors. Give a starting vertex one color, its neighbors the other, and continue. If an edge ever connects two vertices assigned the same color, the graph is not bipartite.

For ordinary undirected graphs, bipartiteness is equivalent to having no odd-length cycle. A triangle fails because its third edge must connect two same-colored vertices. A four-vertex cycle succeeds with alternating colors.

In a data model, explicit side labels can be more useful than rediscovering a partition. NetworkX commonly uses a vertex attribute to identify the two sides, but adding that attribute does not by itself enforce valid edges. Algorithms may expect the caller to supply one side and to ensure the input meets their assumptions.

Bipartite projection creates a graph on just one side, connecting vertices that share neighbors on the other. For example, customers can be connected if they purchased a common product. Projection changes the representation and can lose information about which shared product caused an edge. Popular products can also create very dense projected groups.

Three practical examples

A staffing planner represents workers on one side and tasks on the other, with edges marking qualifications before solving an assignment problem.
A recommendation prototype represents customers and purchased products, retaining which interactions connect the two roles.
A research directory represents authors and papers, allowing collaboration relationships to be derived while preserving the underlying publications.

Think of it this way

Think of a seating chart with guests listed down one side and tables across the top. A marked cell links a guest to a table. Guest-to-guest friendships do not belong in that same two-role relationship.

The analogy captures separation of roles, not an automatic seating solution. Capacity limits, preferences and whether one guest may appear at several tables require additional rules beyond the graph's bipartite structure.

Worked example

From qualifications to an assignment

Let the worker side be {Ada, Ben, Cy} and the task side {Packing, Checking}. Add edges Ada-Packing, Ada-Checking, Ben-Packing and Cy-Checking. Every edge crosses between sides, so the graph is bipartite.

A matching could select Ben-Packing and Ada-Checking. No selected edges share a worker or task, so both tasks receive different workers. Cy remains unmatched. Another valid matching selects Ada-Packing and Cy-Checking.

Selecting Ada-Packing and Ada-Checking is not a matching because the edges share Ada, even though both are valid graph edges. If workers can handle multiple tasks, the planning model needs capacities rather than an ordinary one-to-one matching assumption.

Now project onto workers. Ada and Ben share Packing; Ada and Cy share Checking. Ben and Cy share no task, so they have no projected edge. If one additional task were connected to all workers, it would create a triangle in the worker projection. That would not contradict the original graph being bipartite: projection produces a different graph.

Illustrative case study

Fictional case: Maple Recommendations stores customers and products in one relationship graph. A later feature adds customer-to-customer friendship edges but leaves the data labeled bipartite.

A review notices that algorithms expecting only cross-role interactions now receive a different structure. The team separates the interaction graph from the social graph and records which relationship types each method uses.

The lesson is that descriptive labels do not enforce mathematical properties. A graph that begins with two clean roles can lose its intended structure as new edge types are added.

Common misconceptions and mistakes

Bipartite means the graph has two connected components. It means there are two vertex sets with only cross-set edges.
The two sets must have equal size. Their sizes can differ.
Every cross-set pair must be connected. That is required only for a complete bipartite graph.
A bipartite graph is already a matching. A matching is a selected subset of edges with additional restrictions.
Its one-side projection must remain bipartite. Projection can introduce triangles and other odd cycles.

Business use

Bipartite representations help preserve the meaning of interactions and support matching, allocation and recommendation methods. They are especially useful when the two sides correspond to genuinely different entity roles.

Define each edge precisely: interest, purchase, eligibility and assignment are not interchangeable. Keep role labels and validate new relationships against them. Before projecting, decide whether shared-neighbor identity and frequency must be retained. For assignments, document capacities and objectives separately; bipartiteness alone does not express fairness, workload or preferred allocations.

Check your understanding

Three workers and two tasks have only worker-to-task edges. Does the unequal number of vertices on the two sides prevent bipartiteness?

Answer: No. Equal set sizes are unnecessary. They may affect whether a matching covers every vertex, which is a different question.

Related terms

Assignment problems
Graph partition
two-colouring
odd cycle
matching
complete bipartite graph
bipartite projection
recommendation system
assignment problem

Learn next

Draw the worker-task graph and find all matchings that cover both tasks. Then add a worker-to-worker edge and check whether the original role partition remains valid. Compare preserving role meaning with merely finding some structural two-coloring.

Sources

NetworkX bipartite algorithm documentation, including partition conventions, disconnected-graph ambiguity, matching and projection: https://networkx.org/documentation/stable/reference/algorithms/bipartite.html

The worker assignments and fictional recommendation review are original examples. Their graphs illustrate structure rather than measured operational outcomes.

Previous: Biometric tokenization Next: Birchfield - Tomasi dissimilarity