Bipartite graph

A graph whose vertices can be divided into two disjoint sets so every edge connects vertices in opposite sets. Equivalently, it is a graph with no odd cycle.

Graph theory: The mathematical study of graphs, structures made of vertices joined by edges. Bipartite graphs are a basic graph class defined by how their edges join vertices.
Breadth-first search: A graph traversal that explores vertices in layers of increasing distance from a starting vertex. Layer parity assigns two colors and detects edges that violate bipartiteness.
Bipartite matching: A matching in a bipartite graph, pairing vertices from opposite parts without reusing vertices. It formalizes one-to-one assignments between two kinds of entities.
Complete bipartite graph: A bipartite graph containing every possible edge between its two vertex sets. It is the maximally connected form of a graph with a fixed two-part division.
Vertex coloring: An assignment of colors to graph vertices in which adjacent vertices receive different colors. A graph is bipartite exactly when its vertices can be properly colored with two colors.
Odd cycle: A cycle containing an odd number of edges. Any odd cycle proves that a graph cannot be divided into two independent vertex sets.
Hall's marriage theorem: A theorem giving a necessary and sufficient condition for a bipartite graph to contain a matching covering one part. It characterizes when every vertex on one side can receive a distinct partner.
Complete graph: A graph in which every pair of distinct vertices is joined by an edge. Complete graphs with at least three vertices contain triangles and are not bipartite.
Cycle graph: A graph whose vertices form one closed path, with each vertex joined to its two neighbors. An odd cycle is the obstruction that prevents a graph from being bipartite.
Even cycle: A cycle containing an even number of edges. Unlike odd cycles, even cycles can alternate between the two parts consistently.

Linked from 35 pages