# Complete graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Complete_graph
> Markdown URL: https://mediated.wiki/source/Complete_graph.md
> Source: https://en.wikipedia.org/wiki/Complete_graph
> Source revision: 1352723368
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Graph in which every two vertices are adjacent}}
{{Infobox graph
 | name = Complete graph
 | image = 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''! ([''S''](/source/Symmetric_group)<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
  | [{{math|(''n'' − 1)}}-regular](/source/Regular_graph)
  | [Symmetric graph](/source/Symmetric_graph)
  | [Vertex-transitive](/source/Vertex-transitive_graph)
  | [Edge-transitive](/source/Edge-transitive_graph)
  | [Strongly regular](/source/strongly_regular_graph)
  | [Integral](/source/Integral_graph)
  }}
}}
In the [mathematical](/source/mathematics) field of [graph theory](/source/graph_theory), a '''complete graph''' is a [simple](/source/simple_graph) [undirected graph](/source/undirected_graph) in which every pair of distinct [vertices](/source/vertex_(graph_theory)) is connected by a unique [edge](/source/edge_(graph_theory)).  A '''complete digraph''' is a [directed graph](/source/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| isbn = 978-3-319-71839-2
 }}; see [https://books.google.com/books?id=IHJgDwAAQBAJ&pg=PA17 p. 17]</ref>

Graph theory itself is typically dated as beginning with [Leonhard Euler](/source/Leonhard_Euler)'s 1736 work on the [Seven Bridges of Königsberg](/source/Seven_Bridges_of_K%C3%B6nigsberg). However, [drawing](/source/graph_drawing)s of complete graphs, with their vertices placed on the points of a [regular polygon](/source/regular_polygon), had already appeared in the 13th century, in the work of [Ramon Llull](/source/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|editor-link=Robin Wilson (mathematician)|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](/source/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](/source/triangular_number)), and is a [regular graph](/source/regular_graph) of [degree](/source/degree_(graph_theory)) {{math|''n'' − 1}}.  All complete graphs are their own [maximal cliques](/source/Clique_(graph_theory)). They are maximally [connected](/source/connectivity_(graph_theory)) as the only [vertex cut](/source/vertex_cut) which disconnects the graph is the complete set of vertices. The [complement graph](/source/complement_graph) of a complete graph is an [empty graph](/source/empty_graph).

If the edges of a complete graph are each given an [orientation](/source/Orientation_(graph_theory)), the resulting [directed graph](/source/directed_graph) is called a [tournament](/source/tournament_(graph_theory)).

{{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](/source/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|date=19 February 2020 |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 [paths](/source/Path_(graph_theory)) 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 [Euler's constant](/source/e_(mathematical_constant)), and

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

The number of [matchings](/source/Matching_(graph_theory)) of the complete graphs are given by the [telephone numbers](/source/Telephone_number_(mathematics))
: 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](/source/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](/source/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](/source/perfect_matching)s of the complete graph {{mvar|K{{sub|n}}}} (with {{mvar|n}} even) is given by the [double factorial](/source/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 numbers](/source/Crossing_number_(graph_theory)) 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](/source/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 is the [edge graph](/source/Graph_of_a_polytope) of an {{math|(''n'' − 1)}}-dimensional [simplex](/source/simplex).  Geometrically {{math|''K''{{sub|3}}}} forms the edge set of a [triangle](/source/triangle), {{math|''K''{{sub|4}}}} a [tetrahedron](/source/tetrahedron), etc.  The [Császár polyhedron](/source/Cs%C3%A1sz%C3%A1r_polyhedron), a nonconvex polyhedron with the topology of a [torus](/source/torus), has the complete graph {{math|''K''{{sub|7}}}} as its [skeleton](/source/skeleton_(topology)).<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](/source/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](/source/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](/source/Kuratowski's_theorem), a graph is planar if and only if it contains neither {{math|''K''{{sub|5}}}} nor the [complete bipartite graph](/source/complete_bipartite_graph) {{math|''K''{{sub|3,3}}}} as a subdivision, and by [Wagner's theorem](/source/Wagner's_theorem) the same result holds for [graph minor](/source/graph_minor)s in place of subdivisions.  As part of the [Petersen family](/source/Petersen_family), {{math|''K''{{sub|6}}}} plays a similar role as one of the [forbidden minor](/source/forbidden_minor)s for [linkless embedding](/source/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](/source/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](/source/Hamiltonian_cycle) that is embedded in space as a [nontrivial knot](/source/Knot_(mathematics)).

==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 skin-invert-image"
! {{math|''K''<sub>1</sub>: 0}}
! {{math|''K''<sub>2</sub>: 1}}
! {{math|''K''<sub>3</sub>: 3}}
! {{math|''K''<sub>4</sub>: 6}}
|-
| 140px
| 140px
| 140px
| 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}}
|-
| 140px
| 140px
| 140px
| 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}}
|-
| 140px
| 140px
| 140px
| 140px
|}

==See also==
* [Fully connected network](/source/Network_topology), in computer networking
* [Complete bipartite graph](/source/Complete_bipartite_graph) (or '''biclique'''), a special [bipartite graph](/source/bipartite_graph) where every vertex on one side of the bipartition is connected to every vertex on the other side
* The [simplex](/source/simplex), which is identical to a '''complete graph''' of <math>n+1</math> vertices, where <math>n</math> is the [dimension](/source/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

---
Adapted from the Wikipedia article [Complete graph](https://en.wikipedia.org/wiki/Complete_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Complete_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.