Complete graph

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).
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, appeared already 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 formula_1 vertices is denoted by formula_2. Some sources claim that the letter formula_3 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 formula_3, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.
formula_5 has formula_6 edges (a triangular number), and is a regular graph of degree formula_7. 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.
formula_5 can be decomposed into formula_1 trees formula_10 such that formula_10 has formula_12 vertices. Ringel's conjecture asks if the complete graph formula_13 can be decomposed into copies of any tree with formula_1 edges. This is known to be true for sufficiently large formula_1.
The number of matchings of the complete graphs are given by the telephone numbers
These numbers give the largest possible value of the Hosoya index for an formula_1-vertex graph. The number of perfect matchings of the complete graph formula_5 (with formula_1 even) is given by the double factorial formula_19.
The crossing numbers up to formula_20 are known, with formula_21 requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project. Rectilinear Crossing numbers for formula_5 are 
Geometry and topology.
A complete graph with formula_1 nodes represents the edges of an formula_24-simplex. Geometrically forms the edge set of a triangle, a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton.
 through 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 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 nor the complete bipartite graph 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, plays a similar role as one of the forbidden minors for linkless embedding. In other words, and as Conway and Gordon proved, every embedding of 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 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.
Examples.
Complete graphs on formula_1 vertices, for formula_1 between 1 and 12, are shown below along with the numbers of edges: