Complete graph

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_n. 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_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. Ringel's conjecture asks if the complete graph K_2n+1 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_n+2 is given by

${\displaystyle w_{n+2}=n!e_n=\lfloor en!\rfloor ,}$

where e refers to Euler's constant, and

${\displaystyle 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, ... (sequence A000085 in the OEIS).

These numbers give the largest possible value of the Hosoya index for an n-vertex graph. The number of perfect matchings of the complete graph K_n (with n even) is given by the double factorial (n − 1)!!.

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_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).