Editing Bipartite graph (section)

{{Short description|Graph divided into two independent sets}}
{{multiple image
 | align = right | perrow = 1  | total_width = 230px
 | image1 = Simple bipartite graph; two layers.svg
 | image2 = Simple bipartite graph; no crossings.svg
 | footer = Example of a bipartite graph without cycles
}}
[[File:Biclique K 3 5 bicolor.svg|thumbnail|A [[complete bipartite graph]] with ''m'' = 5 and ''n'' = 3]]
[[File:Heawood graph bipartite (bicolor).svg|thumb|The [[Heawood graph]] is bipartite.]]
In the [[mathematics|mathematical]] field of [[graph theory]], a '''bipartite graph''' (or '''bigraph''') is a [[Graph (discrete mathematics)|graph]] whose [[vertex (graph theory)|vertices]] can be divided into two [[disjoint sets|disjoint]] and [[Independent set (graph theory)|independent sets]] <math>U</math> and <math>V</math>, that is, every [[edge (graph theory)|edge]] connects a [[Vertex (graph theory)|vertex]] in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length [[cycle (graph theory)|cycles]].<ref name=diestel2005graph>{{citation|last=Diestel|first=Reinard|title=Graph Theory|series=[[Graduate Texts in Mathematics]]|year=2005|publisher=Springer|isbn=978-3-642-14278-9|url=http://diestel-graph-theory.com/|access-date=2012-02-27|archive-date=2011-04-09|archive-url=https://web.archive.org/web/20110409144253/http://diestel-graph-theory.com/|url-status=live}}</ref><ref>{{citation
 | last1 = Asratian
 | first1 = Armen S.
 | last2 = Denley
 | first2 = Tristan M. J.
 | last3 = Häggkvist
 | first3 = Roland
 | isbn = 9780521593458
 | publisher = Cambridge University Press
 | series = Cambridge Tracts in Mathematics
 | title = Bipartite Graphs and their Applications
 | volume = 131
 | year = 1998
 | url-access = registration
 | url = https://archive.org/details/bipartitegraphst0000asra
 }}.</ref>

The two sets <math>U</math> and <math>V</math> may be thought of as a [[graph coloring|coloring]] of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> red, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="adh98-7"/><ref name="s12">{{citation
 | last = Scheinerman | first = Edward R. | author-link = Ed Scheinerman
 | edition = 3rd
 | isbn = 9780840049421
 | page = 363
 | publisher = Cengage Learning
 | title = Mathematics: A Discrete Introduction
 | url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
 | year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a [[Gallery of named graphs|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 <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not [[connected graph|connected]], it may have more than one bipartition;<ref>{{citation
 | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
 | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
 | isbn = 9781584888000
 | page = 223
 | publisher = CRC Press
 | series = Discrete Mathematics And Its Applications
 | title = Chromatic Graph Theory
 | url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
 | volume = 53
 | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application.  If <math>|U|=|V|</math>, that is, if the two subsets have equal [[cardinality]], then <math>G</math> is called a ''balanced'' bipartite graph.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> If all vertices on the same side of the bipartition have the same [[Degree (graph theory)|degree]], then <math>G</math> is called [[biregular graph|biregular]].