Editing Complete bipartite graph

{{short description|Bipartite graph where each node of 1st set is linked to all nodes of 2nd set}}
{{infobox graph
 | name = Complete bipartite graph
 | image = [[Image:Biclique_K_3_5.svg|170px]]
 | image_caption = A complete bipartite graph with {{math|1=''m'' = 5}} and {{math|1=''n'' = 3}}
 | automorphisms = <math>\left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & \text{otherwise}\end{array}\right.</math>
 | vertices = {{math|''n'' + ''m''}}
 | edges = {{mvar|mn}}
 | chromatic_number = 2
 | chromatic_index = {{math|max{''m'', ''n''} }}
 | radius = <math>\left\{\begin{array}{ll}1 & m = 1 \vee n = 1\\ 2 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}1 & m = n = 1\\ 2 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & m = 1 \lor n = 1\\ 4 & \text{otherwise}\end{array}\right.</math>
 | spectrum = <math>\left\{0^{n + m - 2}, (\pm\sqrt{nm})^1\right\}</math>
 | notation = {{math|''K''{{sub|''m'',''n''}}}}
}}

In the [[mathematical]] field of [[graph theory]], a '''complete bipartite graph''' or '''biclique''' is a special kind of [[bipartite graph]] where every [[vertex (graph theory)|vertex]] of the first set is connected to every vertex of the second set.<ref name="bm">{{citation
 | last1=Bondy
 | first1=John Adrian
 | author-link1=John Adrian Bondy
 | last2=Murty
 | first2=U. S. R.
 | author-link2=U. S. R. Murty
 | page=[https://archive.org/details/graphtheorywitha0000bond/page/5 5]
 | title=Graph Theory with Applications
 | year=1976
 | publisher=North-Holland
 | isbn=0-444-19451-7
 | url=https://archive.org/details/graphtheorywitha0000bond/page/5
}}.</ref><ref name="d">{{Citation
 | last=Diestel | first=Reinhard | author-link = Reinhard Diestel
 | title=Graph Theory
 | publisher=[[Springer Science+Business Media|Springer]]
 | year=2005
 | edition=3rd
 | isbn=3-540-26182-6
}}. [http://diestel-graph-theory.com/ Electronic edition], page 17.</ref>

Graph theory itself is typically dated as beginning with [[Leonhard Euler]]'s 1736 work on the [[Seven Bridges of Königsberg]]. However, [[graph drawing|drawing]]s of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of [[Ramon Llull]] edited by [[Athanasius Kircher]].<ref name="knuth"/><ref>{{citation|title=An Atlas of Graphs|first1=Ronald C.|last1=Read|first2=Robin J.|last2=Wilson|publisher=Clarendon Press|year=1998|isbn=9780198532897|page=ii}}.</ref> Llull himself had made similar drawings of [[complete graph]]s three centuries earlier.<ref name="knuth">{{citation|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|author-link=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins |contribution-url=https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7 |isbn=978-0191630620}}.
</ref>

== Definition ==
A '''complete bipartite graph''' is a graph whose vertices can be partitioned into two subsets {{math|''V''{{sub|1}}}} and {{math|''V''{{sub|2}}}} such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a [[bipartite graph]] {{math|(''V''{{sub|1}}, ''V''{{sub|2}}, ''E'')}} such that for every two vertices {{math|''v''{{sub|1}} ∈ ''V''{{sub|1}}}} and{{math| ''v''{{sub|2}} ∈ ''V''{{sub|2}}}}, {{math|''v''{{sub|1}}''v''{{sub|2}}}} is an edge in {{mvar|E}}. A complete bipartite graph with partitions of size {{math|1={{abs|''V''{{sub|1}}}} = ''m''}} and {{math|1={{abs|''V''{{sub|2}}}} = ''n''}}, is denoted {{math|''K''{{sub|''m'',''n''}}}};<ref name="bm"/><ref name="d"/> every two graphs with the same notation are [[graph isomorphism|isomorphic]].

== Examples ==
[[File:Star graphs.svg|class=skin-invert-image|thumb|upright=1.8|right|The [[Star (graph theory)|star graphs]] {{math|''K''{{sub|1,3}}}}, {{math|''K''{{sub|1,4}}}}, {{math|''K''{{sub|1,5}}}}, and {{math|''K''{{sub|1,6}}}}.]]
[[File:Zarankiewicz K4 7.svg|class=skin-invert-image|thumb|A complete bipartite graph of {{math|''K''{{sub|4,7}}}} showing that [[Turán's brick factory problem]] with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)]]

* For any {{mvar|k}}, {{math|''K''{{sub|1,''k''}}}} is called a [[Star (graph theory)|star]].<ref name="d"/> All complete bipartite graphs which are [[Tree (graph theory)|trees]] are stars.
** The graph {{math|''K''{{sub|1,3}}}} is called a [[Claw (graph theory)|claw]], and is used to define the [[claw-free graph]]s.<ref>{{citation | last1 = Lovász | first1 = László | author1-link = László Lovász | last2 = Plummer | first2 = Michael D. | author2-link = Michael D. Plummer | isbn = 978-0-8218-4759-6 | mr = 2536865 | page = 109 | publisher = AMS Chelsea |location=Providence, RI | title = Matching theory | url = https://books.google.com/books?id=yW3WSVq8ygcC&pg=PA109 | year = 2009}}. Corrected reprint of the 1986 original.</ref>
* The graph {{math|''K''{{sub|3,3}}}} is called the [[water, gas, and electricity|utility graph]]. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the [[planar graph|nonplanarity]] of {{math|''K''{{sub|3,3}}}}.<ref>{{citation|title=A Logical Approach to Discrete Math | first1=David|last1=Gries|author1-link=David Gries|first2=Fred B.|last2=Schneider|author2-link=Fred B. Schneider | publisher=Springer | year=1993|isbn=9780387941158|page=437|url=https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA437}}.</ref>
* The maximal bicliques found as subgraphs of the digraph of a relation are called '''concepts'''. When a lattice is formed by taking meets and joins of these subgraphs, the relation has an [[heterogeneous relation#Induced concept lattice|Induced concept lattice]]. This type of analysis of relations is called [[formal concept analysis]].
{{clear}}

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

== See also ==
* [[Biclique-free graph]], a class of sparse graphs defined by avoidance of complete bipartite subgraphs
* [[Crown graph]], a graph formed by removing a [[perfect matching]] from a complete bipartite graph
* [[Complete multipartite graph]], a generalization of complete bipartite graphs to more than two sets of vertices
* [[Biclique attack]]

== References ==
{{reflist|30em}}

[[Category:Parametric families of graphs]]