Complete graph

From Wikipedia, the free encyclopedia

Complete graph
K₇, a complete graph with 7 vertices
Vertices	n
Edges	n(n − 1) / 2
This box: view • talk • edit

In the mathematical field of graph theory, a complete graph is a simple graph where every pair of distinct vertices is connected by an edge. The complete graph on Failed to parse (Missing texvc executable; please see math/README to configure.): n

vertices has Failed to parse (Missing texvc executable; please see math/README to configure.): n
vertices and Failed to parse (Missing texvc executable; please see math/README to configure.): n(n-1)/2
edges, and is denoted by Failed to parse (Missing texvc executable; please see math/README to configure.): K_n

. It is a regular graph of degree Failed to parse (Missing texvc executable; please see math/README to configure.): n-1 . All complete graphs are their own cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices.

A complete graph with n-nodes represents the edges of an n-simplex. Geometrically Failed to parse (Missing texvc executable; please see math/README to configure.): K_3

relates to a triangle, Failed to parse (Missing texvc executable; please see math/README to configure.): K_4
a tetrahedron, Failed to parse (Missing texvc executable; please see math/README to configure.): K_5
a pentachoron, etc.

Kuratowski's theorem says that a planar graph cannot contain Failed to parse (Missing texvc executable; please see math/README to configure.): K_5

(or the complete bipartite graph Failed to parse (Missing texvc executable; please see math/README to configure.): K_{3,3}

) as a minor. Since Failed to parse (Missing texvc executable; please see math/README to configure.): K_n

includes Failed to parse (Missing texvc executable; please see math/README to configure.): K_{n-1}

, no complete graph Failed to parse (Missing texvc executable; please see math/README to configure.): K_n

with Failed to parse (Missing texvc executable; please see math/README to configure.): n
greater than or equal to 5 is planar.

An important property of the complete graph is the quadratic number of connections. That is, the number of edges is a quadratic function of the number of nodes. As such, a complete graph can be the worst case for large connected systems like social and computer networks.

Complete graphs on Failed to parse (Missing texvc executable; please see math/README to configure.): n

vertices, for Failed to parse (Missing texvc executable; please see math/README to configure.): n
between 1 and 8, are shown below along with the numbers of connections:

Failed to parse (Missing texvc executable; please see math/README to configure.): K_1: 0	Failed to parse (Missing texvc executable; please see math/README to configure.): K_2: 1	Failed to parse (Missing texvc executable; please see math/README to configure.): K_3: 3	Failed to parse (Missing texvc executable; please see math/README to configure.): K_4: 6

Failed to parse (Missing texvc executable; please see math/README to configure.): K_5: 10	Failed to parse (Missing texvc executable; please see math/README to configure.): K_6: 15	Failed to parse (Missing texvc executable; please see math/README to configure.): K_7: 21	Failed to parse (Missing texvc executable; please see math/README to configure.): K_8: 28