 Complete graph

Complete graph
K_{7}, a complete graph with 7 verticesVertices n Edges Diameter 1 Girth 3 if n ≥ 3 Automorphisms n! (S_{n}) Chromatic number n Chromatic index n if n is odd
n − 1 if n is evenSpectral Gap n Properties (n − 1)regular
Symmetric graph
Vertextransitive
Edgetransitive
Unit distance
Strongly regular
IntegralNotation K_{n} v · 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. Contents
Properties
The complete graph on n vertices has n(n − 1)/2 edges (a triangular number), and is denoted by K_{n} (from the German komplett).^{[1]} It 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.
Geometry and topology
A complete graph with n nodes represents the edges of an (n − 1)simplex. Geometrically K_{3} forms the edge set of a triangle, K_{4} a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K_{7} as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton.
K_{1} through K_{4} 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 K_{5} 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 K_{5} nor the complete bipartite graph K_{3,3} 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, K_{6} plays a similar role as one of the forbidden minors for linkless embedding.^{[2]}
Examples
Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges:
K_{1}: 0 K_{2}: 1 K_{3}: 3 K_{4}: 6 K_{5}: 10 K_{6}: 15 K_{7}: 21 K_{8}: 28 K_{9}: 36 K_{10}: 45 K_{11}: 55 K_{12}: 66 References
 ^ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, SpringerVerlag, p. 436 .
 ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3space", Bulletin of the American Mathematical Society 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S027309791993003355, MR1164063 .
External links
 Weisstein, Eric W., "Complete Graph" from MathWorld.
Categories: Parametric families of graphs
 Regular graphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
complete graph — noun A graph where every pair of vertices is connected by an edge … Wiktionary
Complete bipartite graph — A complete bipartite graph with m = 5 and n = 3 Vertices n + m Edges mn … Wikipedia
Graph pebbling — is a mathematical game and area of interest played on a graph with pebbles on the vertices. Game play is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Graph theory — 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. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium
Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor … Wikipedia
Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… … Wikipedia
Graph homomorphism — Not to be confused with graph homeomorphism. In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices. Contents 1… … Wikipedia
18+© Academic, 20002024 Contact us: Technical Support, Advertising
Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx.Share the article and excerpts
Complete graph
 Complete graph

Complete graph
K_{7}, a complete graph with 7 verticesVertices n Edges Diameter 1 Girth 3 if n ≥ 3 Automorphisms n! (S_{n}) Chromatic number n Chromatic index n if n is odd
n − 1 if n is evenSpectral Gap n Properties (n − 1)regular
Symmetric graph
Vertextransitive
Edgetransitive
Unit distance
Strongly regular
IntegralNotation K_{n}