Editing Complete graph (section)

==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|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 [[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}}.