Complete graph
Graph in which every two vertices are adjacent
title: "Complete graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["parametric-families-of-graphs", "regular-graphs"] description: "Graph in which every two vertices are adjacent" topic_path: "general/parametric-families-of-graphs" source: "https://en.wikipedia.org/wiki/Complete_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Graph in which every two vertices are adjacent ::
::data[format=table title="Infobox graph"]
| Field | Value |
|---|---|
| name | Complete graph |
| image | [[Image:Complete graph K7.svg |
| image_caption | K7, a complete graph with 7 vertices |
| vertices | n |
| radius | \left{\begin{array}{ll}0 & n \le 1\ 1 & \text{otherwise}\end{array}\right. |
| diameter | \left{\begin{array}{ll}0 & n \le 1\ 1 & \text{otherwise}\end{array}\right. |
| girth | \left{\begin{array}{ll}\infty & n \le 2\ 3 & \text{otherwise}\end{array}\right. |
| edges | \textstyle\frac{n(n - 1)}{2} |
| notation | Kn |
| automorphisms | n! (Sn) |
| chromatic_number | n |
| chromatic_index | {{ubl |
| spectrum | \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. |
| properties | {{ubl |
| :: |
| name = Complete graph | image = [[Image:Complete graph K7.svg|200px]] | image_caption = K7, a complete graph with 7 vertices | vertices = n | radius = \left{\begin{array}{ll}0 & n \le 1\ 1 & \text{otherwise}\end{array}\right. | diameter = \left{\begin{array}{ll}0 & n \le 1\ 1 & \text{otherwise}\end{array}\right. | girth = \left{\begin{array}{ll}\infty & n \le 2\ 3 & \text{otherwise}\end{array}\right. | edges = \textstyle\frac{n(n - 1)}{2} |notation = Kn | automorphisms = n! (Sn) | chromatic_number = n | chromatic_index = {{ubl | n if n is odd | n − 1 if n is even | spectrum = \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. | properties = {{ubl | (n − 1)-regular | Symmetric graph | Vertex-transitive | Edge-transitive | Strongly regular | Integral 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).{{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
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.. Such a drawing is sometimes referred to as a mystic rose.
Properties
The complete graph on n vertices is denoted by K. Some sources claim that the letter K in this notation stands for the German word komplett, 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.
K 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 can be decomposed into n trees T such that T has i vertices. Ringel's conjecture asks if the complete graph K can be decomposed into copies of any tree with n edges. This is known to be true for sufficiently large n.
The number of all distinct paths between a specific pair of vertices in K is given by
: w_{n+2} = n! e_n = \lfloor en!\rfloor,
where e refers to Euler's constant, and
:e_n = \sum_{k=0}^n\frac{1}{k!}.
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, ... .
These numbers give the largest possible value of the Hosoya index for an n-vertex graph.{{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
The crossing numbers up to K are known, with K requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project. Rectilinear Crossing numbers for K 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, ... .
Geometry and topology
::figure[src="https://upload.wikimedia.org/wikipedia/commons/d/db/Csaszar_polyhedron_3D_model.svg" caption="date=2017-09-18 }}, Bolyai Institute, University of Szeged, 1949"] ::
A complete graph with n nodes is the edge graph of an (n − 1)-dimensional simplex. Geometrically K forms the edge set of a triangle, K a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K as its skeleton.{{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
K through K 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 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 nor the complete bipartite graph K 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 plays a similar role as one of the forbidden minors for linkless embedding.{{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 }}. In other words, and as Conway and Gordon proved, every embedding of K 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 K contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.
Examples
Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges:
::data[format=table]
| K1: 0 | K2: 1 | K3: 3 | K4: 6 | K5: 10 | K6: 15 | K7: 21 | K8: 28 | K9: 36 | K10: 45 | K11: 55 | K12: 66 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| [[Image:Complete graph K1.svg | 140px]] | [[Image:Complete graph K2.svg | 140px]] | [[Image:Complete graph K3.svg | 140px]] | [[Image:3-simplex graph.svg | 140px]] | ||||
| [[Image:4-simplex graph.svg | 140px]] | [[Image:5-simplex graph.svg | 140px]] | [[Image:6-simplex graph.svg | 140px]] | [[Image:7-simplex graph.svg | 140px]] | ||||
| [[Image:8-simplex graph.svg | 140px]] | [[Image:9-simplex graph.svg | 140px]] | [[Image:10-simplex graph.svg | 140px]] | [[Image:11-simplex graph.svg | 140px]] | ||||
| :: |
References
References
- "Mystic Rose". nrich.maths.org.
- (1993). "A Logical Approach to Discrete Math". Springer-Verlag.
- Pirnot, Thomas L.. (2000). "Mathematics All Around". Addison Wesley.
- (2019-08-05). "Optimal packings of bounded degree trees". [[Journal of the European Mathematical Society]].
- Ringel, G.. (1963). "Theory of Graphs and its Applications".
- (2021). "A proof of Ringel's Conjecture". Geometric and Functional Analysis.
- Hartnett, Kevin. (19 February 2020). "Rainbow Proof Shows Graphs Have Uniform Parts".
- Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
- Callan, David. (2009). "A combinatorial survey of identities for the double factorial".
- Oswin Aichholzer. "Rectilinear Crossing Number project".
- Ákos Császár, [http://www.diale.org/pdf/csaszar.pdf ''A Polyhedron Without Diagonals.''] {{Webarchive. link. (2017-09-18 , Bolyai Institute, University of Szeged, 1949)
- (1983). "Knots and Links in Spatial Graphs". [[Journal of Graph Theory]].
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::