Editing Bipartite graph (section)

===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>