# Complete graph

Complete graph_table_infobox_0

( n − 1 )

2

{\displaystyle \textstyle {\frac {n(n-1)}{2}}}Complete graph_cell_0_2_1

0

n ≤ 1

1

otherwise

{\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_3_1

0

n ≤ 1

1

otherwise

{\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_4_1

n ≤ 2

3

otherwise

{\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_5_1

n = 0

{

0

1

}

n = 1

{

( n − 1

)

1

, −

1

n − 1

}

otherwise

{\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.}Complete graph_cell_0_9_1

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. Complete graph_sentence_0

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). Complete graph_sentence_1

Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. Complete graph_sentence_2

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. Complete graph_sentence_3

Such a drawing is sometimes referred to as a mystic rose. Complete graph_sentence_4

## Properties Complete graph_section_0

The complete graph on n vertices is denoted by Kn. Complete graph_sentence_5

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. Complete graph_sentence_6

Kn has n(n − 1)/2 edges (a triangular number), and is a regular graph of degree n − 1. Complete graph_sentence_7

All complete graphs are their own maximal cliques. Complete graph_sentence_8

They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. Complete graph_sentence_9

The complement graph of a complete graph is an empty graph. Complete graph_sentence_10

If the edges of a complete graph are each given an orientation, the resulting directed graph is called a tournament. Complete graph_sentence_11

Kn can be decomposed into n trees Ti such that Ti has i vertices. Complete graph_sentence_12

Ringel's conjecture asks if the complete graph K2n+1 can be decomposed into copies of any tree with n edges. Complete graph_sentence_13

This is known to be true for sufficiently large n. Complete graph_sentence_14

The number of matchings of the complete graphs are given by the telephone numbers Complete graph_sentence_15

Complete graph_description_list_0

• 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sequence in the OEIS).Complete graph_item_0_0

These numbers give the largest possible value of the Hosoya index for an n-vertex graph. Complete graph_sentence_16

The number of perfect matchings of the complete graph Kn (with n even) is given by the double factorial (n − 1)! Complete graph_sentence_17

!. Complete graph_sentence_18

The crossing numbers up to K27 are known, with K28 requiring either 7233 or 7234 crossings. Complete graph_sentence_19

Further values are collected by the Rectilinear Crossing Number project. Complete graph_sentence_20

Rectilinear Crossing numbers for Kn are Complete graph_sentence_21

Complete graph_description_list_1

• 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 in the OEIS).Complete graph_item_1_1

## Geometry and topology Complete graph_section_1

A complete graph with n nodes represents the edges of an (n − 1)-simplex. Complete graph_sentence_22

Geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. Complete graph_sentence_23

The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K7 as its skeleton. Complete graph_sentence_24

Every neighborly polytope in four or more dimensions also has a complete skeleton. Complete graph_sentence_25

K1 through K4 are all planar graphs. Complete graph_sentence_26

However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph K5 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 K5 nor the complete bipartite graph K3,3 as a subdivision, and by Wagner's theorem the same result holds for graph minors in place of subdivisions. Complete graph_sentence_27

As part of the Petersen family, K6 plays a similar role as one of the forbidden minors for linkless embedding. Complete graph_sentence_28

In other words, and as Conway and Gordon proved, every embedding of K6 into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Complete graph_sentence_29

Conway and Gordon also showed that any three-dimensional embedding of K7 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot. Complete graph_sentence_30

## Examples Complete graph_section_2

Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges: Complete graph_sentence_31

Complete graph_table_general_1