Complete graph
K7, a complete graph with 7 vertices
Vertices	n
Edges	n(n − 1) / 2

In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. The complete graph on n vertices has n vertices and n(n − 1) / 2 edges, and is denoted by K_n. It is a regular graph of degree 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. Image File history File links This is a lossless scalable vector image. ... This article just presents the basic definitions. ... This article just presents the basic definitions. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... This article just presents the basic definitions. ... This article just presents the basic definitions. ... This article just presents the basic definitions. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ... In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex. ... K5, a complete graph. ... In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ... In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ...

A complete graph with n-nodes represents the edges of an n-simplex. Geometrically K₃ relates to a triangle, K₄ a tetrahedron, K₅ a pentachoron, etc. A 3-simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) or n-simplex is an n-dimensional analogue of a triangle. ... A triangle. ... A tetrahedron (plural: tetrahedra) is a polyhedron composed of four triangular faces, three of which meet at each vertex. ... The pentachoron, also called a pentatope or 4-simplex, is the simplest convex regular polychoron (a type of four-dimensional geometric figure). ...

Kuratowski's theorem says that a planar graph cannot contain K₅ (or the complete bipartite graph K_3,3) as a minor. Since K_n includes K_{n − 1}, no complete graph K_n with n greater than or equal to 5 is planar. In graph theory, a planar graph is a graph that can be embedded in the plane so that no edges intersect. ... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ... In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ...

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. f(x) = x2 - x - 2 In mathematics, a quadratic function is a polynomial function of the form , where a is nonzero. ... f(x) = x2 - x - 2 A quadratic function, in mathematics, is a polynomial function of the form , where . ... A social network is a map of the relationships between individuals, indicating the ways in which they are connected through various social familiarities ranging from casual acquaintance to close familial bonds. ... A computer network is a system for communication among two or more computers. ...

Complete graphs on n vertices, for n between 1 and 8, are shown below along with the numbers of connections:

K1:0	K2:1	K3:3	K4:6
K5:10	K6:15	K7:21	K8:28

Image File history File links Complete_graph_K1. ... Image File history File links Complete_graph_K2. ... Image File history File links This is a lossless scalable vector image. ... Image File history File links Complete_graph_K4. ... Image File history File links Complete_graph_K5. ... Image File history File links Complete_graph_K6. ... Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ...

External links

Look up complete graph in Wiktionary, the free dictionary.

• Counting Paths and Cycles in Complete Graphs. Results are available Mehdi Hassani, Cycles in graphs and derangements, Math. Gaz. 88(March 2004) pp. 123-126 (reprint) or here

• Eric W. Weisstein, Complete Graph at MathWorld.