View source for Complete graph

{{Short description|Graph in which every two vertices are adjacent}}
{{Infobox graph
 | name = Complete graph
 | image = [[Image:Complete graph K7.svg|200px]]
 | image_caption = {{math|''K''<sub>7</sub>}}, a complete graph with 7 vertices
 | vertices = {{mvar|n}}
 | radius = <math>\left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right.</math>
 | edges = <math>\textstyle\frac{n(n - 1)}{2}</math>
 |notation = {{math|''K<sub>n</sub>''}}
 | automorphisms    = {{math|''n''! ([[Symmetric group|''S'']]<sub>''n''</sub>)}}
 | chromatic_number = {{mvar|n}}
 | chromatic_index = {{ubl
  | {{mvar|n}} if {{mvar|n}} is odd
  | {{math|''n'' − 1}} if {{mvar|n}} is even
  }}
 | spectrum = <math>\left\{\begin{array}{lll}\emptyset & n = 0\\ \left\{0^1\right\} & n = 1\\ \left\{(n - 1)^1, -1^{n - 1}\right\} & \text{otherwise}\end{array}\right.</math><!-- is n = 1 really necessary? a partial case of the variant "otherwise", isn't it? -->
 | properties = {{ubl
  | [[Regular graph|{{math|(''n'' − 1)}}-regular]]
  | [[Symmetric graph]]
  | [[Vertex-transitive graph|Vertex-transitive]]
  | [[Edge-transitive graph|Edge-transitive]]
  | [[strongly regular graph|Strongly regular]]
  | [[Integral graph|Integral]]
  }}
}}
In the [[mathematics|mathematical]] field of [[graph theory]], a '''complete graph''' is a [[simple graph|simple]] [[undirected graph]] in which every pair of distinct [[vertex (graph theory)|vertices]] is connected by a unique [[edge (graph theory)|edge]].  A '''complete digraph''' is a [[directed graph]] in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction).<ref>{{citation
 | last1 = Bang-Jensen | first1 = Jørgen
 | last2 = Gutin | first2 = Gregory
 | editor1-last = Bang-Jensen | editor1-first = Jørgen
 | editor2-last = Gutin | editor2-first = Gregory
 | contribution = Basic Terminology, Notation and Results
 | doi = 10.1007/978-3-319-71840-8_1
 | pages = 1–34
 | publisher = Springer International Publishing
 | series = Springer Monographs in Mathematics
 | title = Classes of Directed Graphs
 | year = 2018}}; see [https://books.google.com/books?id=IHJgDwAAQBAJ&pg=PA17 p. 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 graphs, with their vertices placed on the points of a [[regular polygon]], had already appeared in the 13th century, in the work of [[Ramon Llull]].<ref>{{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> Such a drawing is sometimes referred to as a '''mystic rose'''.<ref>{{citation|url=https://nrich.maths.org/6703|title=Mystic Rose | publisher=nrich.maths.org |access-date=23 January 2012}}.</ref>

==Properties==
The complete graph on {{mvar|n}} vertices is denoted by {{mvar|K{{sub|n}}}}. Some sources claim that the letter {{mvar|K}} in this notation stands for the German word {{lang|de|komplett}},<ref>{{citation|first1=David|last1=Gries|author1-link=David Gries|first2=Fred B.|last2=Schneider|author2-link=Fred B. Schneider|title=A Logical Approach to Discrete Math|publisher=Springer-Verlag|year=1993|page=436|url=https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA436 |isbn=0387941150}}.</ref> but the German name for a complete graph, {{lang|de|vollständiger Graph}}, does not contain the letter {{mvar|K}}, and other sources state that the notation honors the contributions of [[Kazimierz Kuratowski]] to graph theory.<ref>{{citation|title=Mathematics All Around|first=Thomas L.|last=Pirnot|publisher=Addison Wesley|year=2000|isbn=9780201308150|page=[https://archive.org/details/mathematicsallar0000pirn_2001/page/154 154]|url=https://archive.org/details/mathematicsallar0000pirn_2001/page/154}}.</ref>

{{mvar|K{{sub|n}}}} has {{math|''n''(''n'' – 1)/2}} edges (a [[triangular number]]), and is a [[regular graph]] of [[degree (graph theory)|degree]] {{math|''n'' – 1}}.  All complete graphs are their own [[Clique (graph theory)|maximal cliques]]. They are maximally [[connectivity (graph theory)|connected]] as the only [[vertex cut]] which disconnects the graph is the complete set of vertices. The [[complement graph]] of a complete graph is an [[empty graph]].

If the edges of a complete graph are each given an [[Orientation (graph theory)|orientation]], the resulting [[directed graph]] is called a [[tournament (graph theory)|tournament]].

{{mvar|K{{sub|n}}}} can be decomposed into {{mvar|n}} trees {{mvar|T{{sub|i}}}} such that {{mvar|T{{sub|i}}}} has {{mvar|i}} vertices.<ref>{{Cite journal|last1=Joos|first1=Felix|last2=Kim|first2=Jaehoon|last3=Kühn|first3=Daniela|last4=Osthus|first4=Deryk|date=2019-08-05|title=Optimal packings of bounded degree trees|journal=[[Journal of the European Mathematical Society]]|language=en|volume=21|issue=12|pages=3573–3647|doi=10.4171/JEMS/909|s2cid=119315954|issn=1435-9855|url=http://pure-oai.bham.ac.uk/ws/files/46469651/quasi_random_tree_packing_revised.pdf|access-date=2020-03-09|archive-date=2020-03-09|archive-url=https://web.archive.org/web/20200309181052/http://pure-oai.bham.ac.uk/ws/files/46469651/quasi_random_tree_packing_revised.pdf|url-status=live}}</ref> Ringel's conjecture asks if the complete graph {{math|''K''{{sub|2''n''+1}}}} can be decomposed into copies of any tree with {{mvar|n}} edges.<ref>{{Cite conference|last=Ringel|first=G.|date=1963|title=Theory of Graphs and its Applications|conference=Proceedings of the Symposium Smolenice}}</ref> This is known to be true for sufficiently large {{mvar|n}}.<ref>{{cite journal|last1=Montgomery|first1=Richard|last2=Pokrovskiy|first2=Alexey|last3=Sudakov|first3=Benny|date=2021|title=A proof of Ringel's Conjecture|arxiv=2001.02665|journal=Geometric and Functional Analysis|volume=31|issue=3|pages=663–720|doi=10.1007/s00039-021-00576-2|doi-access=free}}</ref><ref>{{Cite web|url=https://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/|title=Rainbow Proof Shows Graphs Have Uniform Parts|last=Hartnett|first=Kevin|website=Quanta Magazine|language=en|access-date=2020-02-20|archive-date=2020-02-20|archive-url=https://web.archive.org/web/20200220085935/https://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/|url-status=live}}</ref>

The number of all distinct [[Path (graph theory)|paths]] between a specific pair of vertices in {{math|''K''{{sub|''n''+2}}}} is given<ref>Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123&ndash;126, 2004.</ref> by

:<math> w_{n+2} = n! e_n = \lfloor en!\rfloor,</math>

where {{mvar|e}} refers to [[e (mathematical constant)|Euler's constant]], and

:<math>e_n = \sum_{k=0}^n\frac{1}{k!}.</math>

The number of [[Matching (graph theory)|matchings]] of the complete graphs are given by the [[Telephone number (mathematics)|telephone numbers]]
: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... {{OEIS|A000085}}.

These numbers give the largest possible value of the [[Hosoya index]] for an {{mvar|n}}-vertex graph.<ref>{{citation
 | last1 = Tichy
 | first1 = Robert F.
 | last2 = Wagner
 | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | pmid = 16201918
 | citeseerx = 10.1.1.379.8693
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005
 | access-date = 2012-03-29
 | archive-date = 2017-09-21
 | archive-url = https://web.archive.org/web/20170921212603/https://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | url-status = live
 }}.</ref> The number of [[perfect matching]]s of the complete graph {{mvar|K{{sub|n}}}} (with {{mvar|n}} even) is given by the [[double factorial]] {{math|(''n'' – 1)!!}}.<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref>

The [[Crossing number (graph theory)|crossing numbers]] up to {{math|''K''{{sub|27}}}} are known, with {{math|''K''{{sub|28}}}} requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.<ref>{{cite web|url=http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |archive-url=https://web.archive.org/web/20070430141404/http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |url-status=dead |archive-date=2007-04-30 |title=Rectilinear Crossing Number project |author=Oswin Aichholzer }}</ref> Rectilinear Crossing numbers for {{mvar|K{{sub|n}}}} are 
:0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... {{OEIS|A014540}}.

==Geometry and topology==
[[File:Csaszar_polyhedron_3D_model.svg|thumb|100px|Interactive [[Csaszar polyhedron]] model with vertices representing nodes. In [http://upload.wikimedia.org/wikipedia/commons/d/db/Csaszar_polyhedron_3D_model.svg the SVG image], move the mouse to rotate it.<ref>Ákos Császár, [http://www.diale.org/pdf/csaszar.pdf ''A Polyhedron Without Diagonals.''] {{Webarchive|url=https://web.archive.org/web/20170918064243/http://www.diale.org/pdf/csaszar.pdf |date=2017-09-18 }}, Bolyai Institute, University of Szeged, 1949</ref>]]

A complete graph with {{mvar|n}} nodes represents the edges of an {{math|(''n'' – 1)}}-[[simplex]].  Geometrically {{math|''K''{{sub|3}}}} forms the edge set of a [[triangle]], {{math|''K''{{sub|4}}}} a [[tetrahedron]], etc.  The [[Császár polyhedron]], a nonconvex polyhedron with the topology of a [[torus]], has the complete graph {{math|''K''{{sub|7}}}} as its [[skeleton (topology)|skeleton]].<ref>{{citation
  | last = Gardner
  | first = Martin
  | authorlink = Martin Gardner
  | title = Time Travel and Other Mathematical Bewilderments
  | publisher = W. H. Freeman and Company
  | year = 1988
  | pages = 140
  | bibcode = 1988ttom.book.....G
  | isbn = 0-7167-1924-X
  | url = https://archive.org/details/timetravelotherm0000gard_u0o1/mode/2up
  }}</ref> Every [[neighborly polytope]] in four or more dimensions also has a complete skeleton.

{{math|''K''{{sub|1}}}} through {{math|''K''{{sub|4}}}} are all [[planar graph]]s.  However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph {{math|''K''{{sub|5}}}} plays a key role in the characterizations of planar graphs: by [[Kuratowski's theorem]], a graph is planar if and only if it contains neither {{math|''K''{{sub|5}}}} nor the [[complete bipartite graph]] {{math|''K''{{sub|3,3}}}} as a subdivision, and by [[Wagner's theorem]] the same result holds for [[graph minor]]s in place of subdivisions.  As part of the [[Petersen family]], {{math|''K''{{sub|6}}}} plays a similar role as one of the [[forbidden minor]]s for [[linkless embedding]].<ref>{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.1090/S0273-0979-1993-00335-5
 | arxiv = math/9301216 | mr = 1164063
 | issue = 1
 | journal = Bulletin of the American Mathematical Society
 | pages = 84–89
 | title = Linkless embeddings of graphs in 3-space
 | volume = 28
 | year = 1993
| s2cid = 1110662 }}.</ref> In other words, and as Conway and Gordon<ref>{{cite journal |author-link1=J. H. Conway|author-link2=Cameron Gordon (mathematician)|author1=Conway, J. H. |author2=Cameron Gordon|title=Knots and Links in Spatial Graphs |journal=[[Journal of Graph Theory]] |volume=7 |issue=4 |pages=445–453 |year=1983 |doi=10.1002/jgt.3190070410}}</ref> proved, every embedding of {{math|''K''{{sub|6}}}} into three-dimensional space is intrinsically linked, with at least one pair of linked triangles.  Conway and Gordon also showed that any three-dimensional embedding of {{math|''K''{{sub|7}}}} contains a [[Hamiltonian cycle]] that is embedded in space as a [[Knot (mathematics)|nontrivial knot]].

==Examples==
Complete graphs on <math>n</math> vertices, for <math>n</math> between 1 and 12, are shown below along with the numbers of edges:

{|class="wikitable"
! {{math|''K''<sub>1</sub>: 0}}
! {{math|''K''<sub>2</sub>: 1}}
! {{math|''K''<sub>3</sub>: 3}}
! {{math|''K''<sub>4</sub>: 6}}
|-
| [[Image:Complete graph K1.svg|140px]]
| [[Image:Complete graph K2.svg|140px]]
| [[Image:Complete graph K3.svg|140px]]
| [[Image:3-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>5</sub>: 10}}
! {{math|''K''<sub>6</sub>: 15}}
! {{math|''K''<sub>7</sub>: 21}}
! {{math|''K''<sub>8</sub>: 28}}
|-
| [[Image:4-simplex graph.svg|140px]]
| [[Image:5-simplex graph.svg|140px]]
| [[Image:6-simplex graph.svg|140px]]
| [[Image:7-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>9</sub>: 36}}
! {{math|''K''<sub>10</sub>: 45}}
! {{math|''K''<sub>11</sub>: 55}}
! {{math|''K''<sub>12</sub>: 66}}
|-
| [[Image:8-simplex graph.svg|140px]]
| [[Image:9-simplex graph.svg|140px]]
| [[Image:10-simplex graph.svg|140px]]
| [[Image:11-simplex graph.svg|140px]]
|}

==See also==
* [[Network topology#Decentralization|Fully connected network]], in computer networking
* [[Complete bipartite graph]] (or '''biclique'''), a special [[bipartite graph]] where every vertex on one side of the bipartition is connected to every vertex on the other side
* The [[simplex]], which is identical to a '''complete graph''' of <math>n+1</math> vertices, where <math>n</math> is the [[dimension]] of the simplex.

==References==
{{Reflist}}

==External links==
{{Commons}}
{{Wiktionary|complete graph}}
* {{MathWorld | urlname = CompleteGraph | title = Complete Graph}}

{{Authority control}}

[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]