Editing Complete bipartite graph (section)

== Properties ==
{| class="wikitable skin-invert-image" align=right width=360
|+ Example {{math|''K''{{sub|''p'', ''p''}}}} complete bipartite graphs<ref>Coxeter, ''Regular Complex Polytopes'', second edition, p.114</ref>
! {{math|[[Thomsen graph|''K''{{sub|3,3}}]]}}
! {{math|''K''{{sub|4,4}}}}
! {{math|''K''{{sub|5,5}}}}
|-
|[[File:Complex polygon 2-4-3-bipartite graph.png|120px]]
|[[File:Complex polygon 2-4-4 bipartite graph.png|120px]]
|[[File:Complex polygon 2-4-5-bipartite graph.png|120px]]
|- align=center
|[[File:Complex polygon 2-4-3.png|120px]]<BR>3 edge-colorings
|[[File:Complex polygon 2-4-4.png|120px]]<BR>4 edge-colorings
|[[File:Complex polygon 2-4-5.png|120px]]<BR>5 edge-colorings
|-
|colspan=3|[[Regular complex polygon]]s of the form {{math|2{4}''p''}} have ''complete bipartite graphs'' with {{math|2''p''}} vertices (red and blue) and {{math|''p''{{sup|2}}}} 2-edges. They also can also be drawn as {{mvar|p}} edge-colorings.
|}
*Given a bipartite graph, testing whether it contains a complete bipartite subgraph {{math|''K''{{sub|''i'',''i''}}}} for a parameter&nbsp;{{mvar|i}} is an [[NP-complete]] problem.<ref>{{citation
 | last1=Garey
 | first1=Michael R.
 | author-link1=Michael R. Garey
 | last2=Johnson
 | first2=David S.
 | author-link2=David S. Johnson
 | contribution=[GT24] Balanced complete bipartite subgraph
 | page=[https://archive.org/details/computersintract0000gare/page/196 196]
 | year=1979
 | title=[[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | publisher=[[W. H. Freeman|W.&nbsp;H.&nbsp;Freeman]]
 | isbn=0-7167-1045-5
 }}.</ref>
*A [[planar graph]] cannot contain {{math|''K''{{sub|3,3}}}} as a [[minor (graph theory)|minor]]; an [[outerplanar graph]] cannot contain {{math|''K''{{sub|3,2}}}} as a minor (These are not [[sufficient condition]]s for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either {{math|''K''{{sub|3,3}}}} or the [[complete graph]] {{math|''K''{{sub|5}}}} as a minor; this is [[Wagner's theorem]].<ref>{{harvnb|Diestel|2005|p=105}}</ref>
*Every complete bipartite graph. {{math|'''K'''{{sub|''n'',''n''}}}} is a [[Moore graph]] and a {{math|(''n'',4)}}-[[cage (graph theory)|cage]].<ref>{{citation|title=Algebraic Graph Theory|first=Norman|last=Biggs|publisher=Cambridge University Press|year=1993|isbn=9780521458979|page=181|url=https://books.google.com/books?id=6TasRmIFOxQC&pg=PA181}}.</ref>
*The complete bipartite graphs {{math|'''K'''{{sub|''n'',''n''}}}} and {{math|'''K'''{{sub|''n'',''n''+1}}}} have the maximum possible number of edges among all [[triangle-free graph]]s with the same number of vertices; this is [[Mantel's theorem]]. Mantel's result was generalized to {{mvar|k}}-partite graphs and graphs that avoid larger [[Clique (graph theory)|cliques]] as subgraphs in [[Turán's theorem]], and these two complete bipartite graphs are examples of [[Turán graph]]s, the extremal graphs for this more general problem.<ref>{{citation|title=Modern Graph Theory|volume=184|series=[[Graduate Texts in Mathematics]]|first=Béla|last=Bollobás|author-link=Béla Bollobás|publisher=Springer|year=1998|isbn=9780387984889|page=104|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA104}}.</ref>
*The complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has a [[vertex covering number]] of {{math|'''min'''{''m'', ''n''} }} and an [[edge covering number]] of {{math|'''max'''{''m'', ''n''}.}}
*The complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has a [[maximum independent set]] of size {{math|'''max'''{''m'', ''n''}.}}
*The [[adjacency matrix]] of a complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has eigenvalues {{math|{{radic|''nm''}}}}, {{math|−{{radic|''nm''}}}} and 0; with multiplicity 1, 1 and {{math|''n'' + ''m'' − 2}} respectively.<ref>{{harvtxt|Bollobás|1998}}, p.&nbsp;266.</ref>
*The [[Laplacian matrix]] of a complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has eigenvalues {{math|''n'' + ''m''}}, {{mvar|n}}, {{mvar|m}}, and 0; with multiplicity 1, {{math|''m'' − 1}}, {{math|''n'' − 1}} and 1 respectively.
*A complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has {{math|''m''{{sup|''n''−1}} ''n''{{sup|''m''−1}}}} [[spanning tree]]s.<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematic|first=Dieter|last=Jungnickel|author-link=Dieter Jungnickel|publisher=Springer|year=2012|isbn=9783642322785|page=557|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA557}}.</ref>
*A complete bipartite graph {{math|'''K'''{{sub|''m'',''n''}}}} has a [[maximum matching]] of size {{math|'''min'''{''m'',''n''}.}}
*A complete bipartite graph {{math|'''K'''{{sub|''n'',''n''}}}} has a proper [[edge coloring|{{mvar|n}}-edge-coloring]] corresponding to a [[Latin square]].<ref>{{citation|title=Graph Coloring Problems|volume=39|series=Wiley Series in Discrete Mathematics and Optimization|first1=Tommy R.|last1=Jensen|first2=Bjarne|last2=Toft|publisher=Wiley |year=2011|isbn=9781118030745|page=16|url=https://books.google.com/books?id=leL0Y5N0bFoC&pg=PA16}}.</ref>
*Every complete bipartite graph is a [[modular graph]]: every triple of vertices has a median that belongs to shortest paths between each pair of vertices.<ref>{{citation
 | last1 = Bandelt | first1 = H.-J.
 | last2 = Dählmann | first2 = A.
 | last3 = Schütte | first3 = H.
 | doi = 10.1016/0166-218X(87)90058-8
 | issue = 3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 878021
 | pages = 191–215
 | title = Absolute retracts of bipartite graphs
 | volume = 16
 | year = 1987
 | doi-access = free
 }}.</ref>