Editing Complete graph (section)

{{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| 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]]'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>