Movatterモバイル変換

Complete graph

From Wikipedia, the free encyclopedia

Graph in which every two vertices are adjacent

Complete graph
K₇, a complete graph with 7 vertices
Vertices	n
Edges	$\textstyle {\frac {n(n-1)}{2}}$
Radius	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
Diameter	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
Girth	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.$
Automorphisms	n! (S_n)
Chromatic number	n
Chromatic index	n ifn is odd n − 1 ifn is even
Spectrum	$\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.$
Properties	(n − 1)-regular Symmetric graph Vertex-transitive Edge-transitive Strongly regular Integral
Notation	K_n
Table of graphs and parameters

In themathematical field ofgraph theory, acomplete graph is asimple undirected graph in which every pair of distinctvertices is connected by a uniqueedge. Acomplete digraph is adirected graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction).^[1]

Graph theory itself is typically dated as beginning withLeonhard Euler's 1736 work on theSeven Bridges of Königsberg. However,drawings of complete graphs, with their vertices placed on the points of aregular polygon, had already appeared in the 13th century, in the work ofRamon Llull.^[2] Such a drawing is sometimes referred to as amystic rose.^[3]

Properties

[edit]

The complete graph onn vertices is denoted byK_n. Some sources claim that the letterK in this notation stands for the German wordkomplett,^[4] but the German name for a complete graph,vollständiger Graph, does not contain the letterK, and other sources state that the notation honors the contributions ofKazimierz Kuratowski to graph theory.^[5]

K_n hasn(n − 1)/2 edges (atriangular number), and is aregular graph ofdegreen − 1. All complete graphs are their ownmaximal cliques. They are maximallyconnected as the onlyvertex cut which disconnects the graph is the complete set of vertices. Thecomplement graph of a complete graph is anempty graph.

If the edges of a complete graph are each given anorientation, the resultingdirected graph is called atournament.

K_n can be decomposed inton treesT_i such thatT_i hasi vertices.^[6] Ringel's conjecture asks if the complete graphK_2n+1 can be decomposed into copies of any tree withn edges.^[7] This is known to be true for sufficiently largen.^[8]^[9]

The number of all distinctpaths between a specific pair of vertices inK_n+2 is given^[10] by

w_{n+2}=n!e_{n}=\lfloor en!\rfloor ,

wheree refers toEuler's constant, and

e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.

The number ofmatchings of the complete graphs are given by thetelephone numbers

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sequenceA000085 in theOEIS).

These numbers give the largest possible value of theHosoya index for ann-vertex graph.^[11] The number ofperfect matchings of the complete graphK_n (withn even) is given by thedouble factorial(n − 1)!!.^[12]

Thecrossing numbers up toK₂₇ are known, withK₂₈ requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.^[13] Rectilinear Crossing numbers forK_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, ... (sequenceA014540 in theOEIS).

Geometry and topology

[edit]

InteractiveCsaszar polyhedron model with vertices representing nodes. Inthe SVG image, move the mouse to rotate it.^[14]

A complete graph withn nodes is theedge graph of an(n − 1)-dimensionalsimplex. GeometricallyK₃ forms the edge set of atriangle,K₄ atetrahedron, etc. TheCsászár polyhedron, a nonconvex polyhedron with the topology of atorus, has the complete graphK₇ as itsskeleton.^[15] Everyneighborly polytope in four or more dimensions also has a complete skeleton.

K₁ throughK₄ are allplanar graphs. However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graphK₅ plays a key role in the characterizations of planar graphs: byKuratowski's theorem, a graph is planar if and only if it contains neitherK₅ nor thecomplete bipartite graphK_3,3 as a subdivision, and byWagner's theorem the same result holds forgraph minors in place of subdivisions. As part of thePetersen family,K₆ plays a similar role as one of theforbidden minors forlinkless embedding.^[16] In other words, and as Conway and Gordon^[17] proved, every embedding ofK₆ into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Conway and Gordon also showed that any three-dimensional embedding ofK₇ contains aHamiltonian cycle that is embedded in space as anontrivial knot.