Complete graph
Complete graph  

K_{7}, a complete graph with 7 vertices  
Vertices  n 
Edges  [math]\displaystyle{ \textstyle\frac{n(n  1)}{2} }[/math] 
Radius  [math]\displaystyle{ \left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right. }[/math] 
Diameter  [math]\displaystyle{ \left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right. }[/math] 
Girth  [math]\displaystyle{ \left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right. }[/math] 
Automorphisms  n! (S_{n}) 
Chromatic number  n 
Chromatic index 

Spectrum  [math]\displaystyle{ \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] 
Properties  
Notation  K_{n} 
Table of graphs and parameters 
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique 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).^{[1]}
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings 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.^{[2]} Such a drawing is sometimes referred to as a mystic rose.^{[3]}
Properties
The complete graph on n vertices is denoted by K_{n}. Some sources claim that the letter K in this notation stands for the German word komplett,^{[4]} but the German name for a complete graph, vollständiger Graph, does not contain the letter K, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.^{[5]}
K_{n} has n(n – 1)/2 edges (a triangular number), and is a regular graph of degree n – 1. All complete graphs are their own maximal cliques. They are maximally 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, the resulting directed graph is called a tournament.
K_{n} can be decomposed into n trees T_{i} such that T_{i} has i vertices.^{[6]} Ringel's conjecture asks if the complete graph K_{2n+1} can be decomposed into copies of any tree with n edges.^{[7]} This is known to be true for sufficiently large n.^{[8]}^{[9]}
The number of all distinct paths between a specific pair of vertices in K_{n+2} is given^{[10]} by
 [math]\displaystyle{ w_{n+2} = n! e_n = \lfloor en!\rfloor, }[/math]
where e refers to Euler's constant, and
 [math]\displaystyle{ e_n = \sum_{k=0}^n\frac{1}{k!}. }[/math]
The number of matchings of the complete graphs are given by the telephone numbers
 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sequence A000085 in the OEIS).
These numbers give the largest possible value of the Hosoya index for an nvertex graph.^{[11]} The number of perfect matchings of the complete graph K_{n} (with n even) is given by the double factorial (n – 1)!!.^{[12]}
The crossing numbers up to K_{27} are known, with K_{28} requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.^{[13]} Rectilinear Crossing numbers for K_{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, ... (sequence A014540 in the OEIS).
Geometry and topology
A complete graph with n nodes represents the edges of an (n – 1)simplex. Geometrically K_{3} forms the edge set of a triangle, K_{4} a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K_{7} as its skeleton.^{[15]} Every neighborly polytope in four or more dimensions also has a complete skeleton.
K_{1} through K_{4} are all planar graphs. However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph K_{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 K_{5} nor the complete bipartite graph K_{3,3} as a subdivision, and by Wagner's theorem the same result holds for graph minors in place of subdivisions. As part of the Petersen family, K_{6} plays a similar role as one of the forbidden minors for linkless embedding.<ref>{{citation
 doi = 10.1090/S027309791993003355  arxiv = math/9301216  mr = 1164063  issue = 1  journal = Bulletin of the American Mathematical Society  pages = 84–89  title = Linkless embeddings of graphs in 3space  volume = 28  year = 1993
Examples
Complete graphs on [math]\displaystyle{ n }[/math] vertices, for [math]\displaystyle{ n }[/math] between 1 and 12, are shown below along with the numbers of edges:
K_{1}: 0  K_{2}: 1  K_{3}: 3  K_{4}: 6 

K_{5}: 10  K_{6}: 15  K_{7}: 21  K_{8}: 28 
K_{9}: 36  K_{10}: 45  K_{11}: 55  K_{12}: 66 
See also
 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
References
 ↑ BangJensen, Jørgen; Gutin, Gregory (2018), "Basic Terminology, Notation and Results", in BangJensen, Jørgen; Gutin, Gregory, Classes of Directed Graphs, Springer Monographs in Mathematics, Springer International Publishing, pp. 1–34, doi:10.1007/9783319718408_1; see p. 17
 ↑ Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 9780191630620, https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7.
 ↑ Mystic Rose, nrich.maths.org, https://nrich.maths.org/6703, retrieved 23 January 2012.
 ↑ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, SpringerVerlag, p. 436, ISBN 0387941150, https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA436.
 ↑ Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p. 154, ISBN 9780201308150, https://archive.org/details/mathematicsallar0000pirn_2001/page/154.
 ↑ Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (20190805). "Optimal packings of bounded degree trees" (in en). Journal of the European Mathematical Society 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN 14359855. http://pureoai.bham.ac.uk/ws/files/46469651/quasi_random_tree_packing_revised.pdf. Retrieved 20200309.
 ↑ Ringel, G. (1963). "Theory of Graphs and its Applications". Proceedings of the Symposium Smolenice.
 ↑ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). "A proof of Ringel's Conjecture". Geometric and Functional Analysis 31 (3): 663–720. doi:10.1007/s00039021005762.
 ↑ Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts" (in en). https://www.quantamagazine.org/mathematiciansproveringelsgraphtheoryconjecture20200219/.
 ↑ Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
 ↑ Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry", Journal of Computational Biology 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918, http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf, retrieved 20120329.
 ↑ Callan, David (2009), A combinatorial survey of identities for the double factorial, Bibcode: 2009arXiv0906.1317C.
 ↑ Oswin Aichholzer. "Rectilinear Crossing Number project". http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/.
 ↑ Ákos Császár, A Polyhedron Without Diagonals. , Bolyai Institute, University of Szeged, 1949
 ↑ Gardner, Martin (1988), Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, pp. 140, ISBN 071671924X, Bibcode: 1988ttom.book.....G, https://archive.org/details/timetravelotherm0000gard_u0o1/mode/2up
External links
Wikimedia Commons has media related to Complete graph. 
Original source: https://en.wikipedia.org/wiki/Complete graph.
Read more 