Editing Bipartite graph (section)

==Properties==

===Characterization===
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 (graph theory)|cycle]].<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [[Dénes Kőnig]]. For infinite graphs, this result requires the [[axiom of choice]].</ref><ref>{{citation
| last1 = Bang-Jensen
| first1 = Jørgen
| last2 = Gutin
| first2 = Gregory
| title = Digraphs: Theory, Algorithms and Applications
| year = 2001
| isbn = 9781852332686
| page = 25
| publisher = Springer
| edition = 1st
| url = https://www.cs.rhul.ac.uk/books/dbook/main.pdf
| access-date = 2023-01-02
| archive-date = 2023-01-02
| archive-url = https://web.archive.org/web/20230102185916/https://www.cs.rhul.ac.uk/books/dbook/main.pdf
| url-status = live
}}</ref>
* A graph is bipartite if and only if it is 2-colorable, (i.e. its [[chromatic number]] is less than or equal to 2).<ref name="adh98-7"/>
* A graph is bipartite if and only if every edge belongs to an odd number of [[Cut (graph theory)|bonds]], minimal subsets of edges whose removal increases the number of components of the graph.<ref>{{citation
 | last = Woodall | first = D. R.
 | doi = 10.1016/0012-365X(90)90380-Z
 | issue = 2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1071664
 | pages = 217–220
 | title = A proof of McKee's Eulerian-bipartite characterization
 | volume = 84
 | year = 1990| doi-access = 
 }}</ref> 
* A graph is bipartite if and only if the [[Spectral graph theory|spectrum]] of the graph is symmetric.<ref>{{citation
 | last = Biggs | first = Norman
 | edition = 2nd
 | isbn = 9780521458979
 | page = 53
 | publisher = Cambridge University Press
 | series = Cambridge Mathematical Library
 | title = Algebraic Graph Theory
 | url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53
 | year = 1994}}.</ref>

===Kőnig's theorem and perfect graphs===
In bipartite graphs, the size of [[minimum vertex cover]] is equal to the size of the [[maximum matching]]; this is [[Kőnig's theorem (graph theory)|Kőnig's theorem]].<ref>{{citation
  | author = Kőnig, Dénes
  | author-link = Dénes Kőnig
  | title = Gráfok és mátrixok
  | journal = Matematikai és Fizikai Lapok
  | volume = 38
  | year = 1931
  | pages = 116–119}}.</ref><ref>{{citation
 | last1 = Gross | first1 = Jonathan L.
 | last2 = Yellen | first2 = Jay
 | edition = 2nd
 | isbn = 9781584885054
 | page = 568
 | publisher = CRC Press
 | series = Discrete Mathematics And Its Applications
 | title = Graph Theory and Its Applications
 | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568
 | year = 2005}}.</ref> 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 vertex|isolated vertices]] the size of the [[minimum edge cover]] plus the size of a maximum matching equals the number of vertices.<ref>{{citation
 | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
 | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
 | isbn = 9780486483689
 | pages = 189–190
 | publisher = Courier Dover Publications
 | title = A First Course in Graph Theory
 | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189
 | year = 2012}}.</ref> 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 graph]]s: every bipartite graph, the [[complement (graph theory)|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 [[complement (graph theory)|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.<ref>{{citation|title=Modern Graph Theory
|volume= 184 |series= Graduate Texts in Mathematics
|author=Béla Bollobás|publisher	=Springer|year= 1998
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> 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 (graph theory)|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.<ref>{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | doi = 10.4007/annals.2006.164.51
 | issue = 1
 | journal = [[Annals of Mathematics]]
 | pages = 51–229
 | title = The strong perfect graph theorem
 | volume = 164
 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070| s2cid = 119151552 }}.</ref> It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.<ref>{{citation|url=http://www.sfu.ca/~mdevos/notes/graph/345_matchings.pdf|title=Matchings|publisher=Simon Fraser University|first=Matt|last=DeVos|work=Lecture notes: Introduction to Graph Theory, Math 345}}</ref>

===Degree===
For a vertex, the number of adjacent vertices is called the [[degree (graph theory)|degree]] of the vertex and is denoted <math>\deg v</math>. The [[degree sum formula]] for a bipartite graph states that<ref>{{citation|title=Combinatorial Problems and Exercises|first=László|last=Lovász|author-link=László Lovász|edition=2nd|publisher=Elsevier|year=2014|isbn=9780080933092|page=281|url=https://books.google.com/books?id=wvHiBQAAQBAJ&pg=PA281}}</ref>
:<math>\sum_{v \in V} \deg v = \sum_{u \in U} \deg u = |E|\, .</math>

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph ''K''<sub>3,5</sub> has degree sequence <math>(5,5,5), (3,3,3,3,3)</math>. [[Graph isomorphism|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===
The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> 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 <math>(U,V,E)</math> may be used to model a hypergraph in which {{mvar|U}} is the set of vertices of the hypergraph, {{mvar|V}} is the set of hyperedges, and {{mvar|E}} contains an edge from a hypergraph vertex {{mvar|v}} to a hypergraph edge {{mvar|e}} exactly when {{mvar|v}} is one of the endpoints of {{mvar|e}}. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the [[incidence matrix|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 (graph theory)|degree]] two.<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (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 {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation
 | last1 = Brualdi | first1 = Richard A.
 | last2 = Harary | first2 = Frank | author2-link = Frank Harary
 | last3 = Miller | first3 = Zevi
 | doi = 10.1002/jgt.3190040107
 | mr = 558453
 | issue = 1
 | journal = [[Journal of Graph Theory]]
 | pages = 51–73
 | title = Bigraphs versus digraphs via matrices
 | volume = 4
 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
 | doi = 10.4153/CJM-1958-052-0
 | last1 = Dulmage | first1 = A. L.
 | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
 | mr = 0097069
 | journal = Canadian Journal of Mathematics
 | pages = 517–534
 | title = Coverings of bipartite graphs
 | volume = 10
 | year = 1958| s2cid = 123363425 | doi-access = free
 }}.</ref> In this construction, the bipartite graph is the [[bipartite double cover]] of the directed graph.