Complete graph
A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by exactly one edge.[1] The complete graph on n vertices is denoted by K_n, where n ≥ 1, and it represents the most connected simple graph possible on that vertex set.[1] For n = 1, K_1 is a single isolated vertex; for n = 2, K_2 is a single edge; and for larger n, it forms a fully interconnected structure without loops or multiple edges.[2] The number of edges in K_n is given by the binomial coefficient \binom{n}{2} = \frac{n(n-1)}{2}, which counts all possible pairs among the vertices.[1] Every vertex in Kn has degree n-1, making the graph (n-1)-regular and highly symmetric, with the automorphism group isomorphic to the symmetric group Sn.[3] Key properties include its chromatic number of n, requiring n colors for proper vertex coloring, and the chromatic polynomial (z)_n = z(z-1)\cdots(z-n+1).[1] Additionally, K_n is Hamiltonian for n ≥ 3, containing a cycle that visits every vertex exactly once, and the number of spanning trees is n^{n-2} by Cayley's formula.[3] For planarity, K_n is planar only for n ≤ 4 and nonplanar for n ≥ 5, as it contains a subdivision of K_5, violating Kuratowski's theorem.[1] Complete graphs play a central role in graph theory as benchmarks for extremal problems, connectivity, and coloring.[3] They form the foundation of Ramsey theory, where the Ramsey number r(k,l) determines the smallest n such that any graph on n vertices contains a clique of size k or an independent set of size l, with K_n embodying the complete clique.[3] In extremal graph theory, theorems like Turán's address the maximum edges in a graph without a K_r subgraph, while Dirac's and Ore's theorems use degree conditions inspired by complete graphs to guarantee Hamiltonicity.[3] Applications extend to network design, combinatorial optimization, and modeling fully connected systems in computer science and operations research.[3]Definition and Notation
Formal Definition
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.[1] This structure ensures that the graph is maximally connected among simple graphs on the same vertex set, with no additional edges possible without violating simplicity.[4] A simple graph, by definition, contains no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices, while the undirected nature means that edges lack direction and adjacency is symmetric.[5] In this context, the complete graph embodies the strongest form of connectivity for undirected simple graphs, where the absence of self-loops and parallel edges maintains its foundational purity.[6] The concept of a complete graph traces its early visual representation to the 13th century in the logical diagrams of Ramon Llull, a Catalan philosopher and theologian, where such interconnected figures—known as the "mystic rose"—served mnemonic and combinatorial purposes in his Ars Magna system, predating modern graph theory by centuries.[7]Notation and Conventions
The standard notation for a complete graph on n vertices is K_n, where n is a positive integer representing the number of vertices.[1] This symbol, introduced in foundational graph theory texts, succinctly denotes the graph where every pair of distinct vertices is connected by a unique edge.[8] In graph theory literature, complete graphs are conventionally treated as unlabeled structures, meaning they are considered up to isomorphism rather than with fixed vertex labels.[9] All complete graphs on n vertices are isomorphic to one another, as any bijection between their vertex sets preserves the adjacency relations; labeled variants, where vertices are distinguished by identifiers, are used only in contexts requiring specific vertex distinctions, such as algorithmic implementations or matrix representations.[9] The complement of K_n is the empty graph on n vertices, denoted \overline{K_n} or E_n, which consists of n isolated vertices with no edges.[10][8] This relation highlights the duality between complete and empty graphs, where the complement operation inverts the edge set while preserving the vertex set.[10] The notation K_n serves as a fundamental building block in broader graph theory constructions, such as complete multipartite graphs.[11]Structural Properties
Number of Vertices and Edges
A complete graph K_n is defined with n vertices, where every pair of distinct vertices is connected by exactly one undirected edge, resulting in the maximum possible number of edges for a simple graph on n vertices. The total number of edges is given by the binomial coefficient \binom{n}{2}, which equals \frac{n(n-1)}{2}. This formula arises from the combinatorial principle that each edge corresponds to a unique unordered pair of vertices chosen from the n available, ensuring no self-loops or multiple edges.[1][12] The sequence of edge counts for complete graphs K_n as n increases—0 for n=1, 1 for n=2, 3 for n=3, 6 for n=4, and so on—corresponds to the triangular numbers, specifically the (n-1)-th triangular number T_{n-1} = \frac{(n-1)n}{2}. These values form the integer sequence A000217 in the On-Line Encyclopedia of Integer Sequences (OEIS), highlighting the close relationship between complete graphs and the summation of the first k natural numbers for k = n-1. For example, in K_5, there are 10 edges, matching T_4 = 10.[1][13] In matrix representation, the adjacency matrix of K_n is an n \times n symmetric matrix with zeros along the main diagonal (to exclude self-loops) and ones in all off-diagonal positions, formally expressed as A = J_n - I_n, where J_n is the all-ones matrix and I_n is the identity matrix. This structure directly encodes the complete connectivity: the entry A_{ij} = 1 for i \neq j indicates an edge between vertices i and j.[1]Degrees and Regularity
In a complete graph K_n with n vertices, where n \geq 1, each vertex is adjacent to every other distinct vertex, resulting in a degree of n-1 for every vertex.[14] This uniform degree across all vertices establishes K_n as a regular graph of degree n-1.[15] The regularity of K_n follows directly from its definition: since the graph includes all possible edges between distinct vertices, no vertex is excluded from connections to any others, ensuring identical adjacency counts for all.[16] For the trivial case K_1, the single vertex has degree 0, which is consistent with 0-regularity in the degenerate sense, though typically regularity is discussed for n \geq 2.[14] Applying the handshaking lemma to K_n, the sum of all vertex degrees equals n(n-1), which is twice the number of edges, confirming the lemma's validity: \sum_{v \in V} \deg(v) = 2|E| = n(n-1).[17] This equality underscores the structural balance in complete graphs, where the total degree sum aligns precisely with the exhaustive edge connections.[15]Graph-Theoretic Properties
Connectivity and Distances
In a complete graph K_n with n \geq 2 vertices, the vertex connectivity is n-1, meaning that the removal of fewer than n-1 vertices leaves the graph connected, and this value equals the degree of each vertex.[18] This high connectivity reflects the graph's structure, where every vertex is adjacent to all others, ensuring robust linkage.[18] The diameter of K_n for n > 1 is 1, as the longest shortest path between any two distinct vertices is a single edge.[19] Similarly, the radius is also 1, since the eccentricity of every vertex—the maximum distance to any other vertex—is 1.[19] These properties underscore the complete graph's efficiency in traversal, with no vertex more than one step away from any other. For n \geq 3, the girth of K_n is 3, determined by the smallest cycles, which are triangles formed by any three vertices.[20] This minimal girth highlights the abundance of short cycles inherent in the complete structure.Chromatic Number and Cliques
The chromatic number of the complete graph K_n, denoted \chi(K_n), is equal to n. This follows directly from the fact that every pair of vertices in K_n is adjacent, requiring a distinct color for each vertex to avoid adjacent vertices sharing the same color.[1] As the quintessential example of a clique, K_n forms a complete clique on n vertices, where the clique number \omega(K_n) is n, representing the size of the largest clique in the graph. This structure implies that the independence number \alpha(K_n), the size of the largest independent set, is 1, since any two vertices are adjacent and thus cannot both be included in an independent set.[1][21] Complete graphs are perfect graphs, satisfying the condition that for every induced subgraph H, the chromatic number equals the clique number, i.e., \chi(H) = \omega(H). In K_n, every induced subgraph is itself a complete graph K_m for some m \leq n, where \chi(K_m) = \omega(K_m) = m, ensuring the equality holds throughout.[22][1]Decompositions and Substructures
Edge Decompositions
A key aspect of edge decompositions in complete graphs involves partitioning the edge set into spanning subgraphs with specific structures, such as matchings or paths and cycles, which leverage the high connectivity and regularity of K_n. For the complete graph K_{2m} on an even number of vertices, the edges can be decomposed into $2m-1 perfect matchings, known as a 1-factorization. This decomposition exists because K_{2m} is (2m-1)-regular, and each perfect matching covers all vertices exactly once, partitioning the edges completely. The construction, attributed to Walecki in the 1890s, places $2m-1 vertices on a circle and the remaining vertex at the center, pairing the center to one vertex and connecting opposite points on the circle for each matching, then rotating the configuration.[23] This 1-factorization relates to broader studies of resolvable balanced incomplete block designs and has applications in scheduling and network design. In contrast, for K_{2m+1} on an odd number of vertices, the edges decompose into m edge-disjoint Hamiltonian cycles. Each such cycle spans all $2m+1 vertices, and since the graph is $2m-regular with each cycle contributing degree 2, exactly m cycles cover all edges. Walecki's construction achieves this by fixing one vertex and arranging the others in a regular $2m-gon, forming a zigzag cycle through alternate vertices and the fixed point, then rotating the pattern m times.[24] This result, also known as Lucas' theorem, dates to the late 19th century and underpins decompositions in tournament scheduling. Walecki's construction extends to decomposing K_{2m} into m edge-disjoint Hamiltonian paths. For even order, the odd degree $2m-1 requires paths rather than cycles, with each path spanning $2m-1 edges and endpoints receiving degree 1 to balance the decomposition. The method involves a similar rotational symmetry: arrange vertices in two parallel lines of m each, connect them in a serpentine pattern for one path, and rotate or reflect to generate the remaining m-1 paths. This partitions all m(2m-1) edges exactly.[25] Recent advances in edge decompositions include the 2020 proof of Ringel's conjecture by Montgomery, Pokrovskiy, and Sudakov, establishing that any tree with n edges packs $2n+1 edge-disjoint copies into K_{2n+1}, providing a generalization beyond paths and cycles for sufficiently large n.[25]Matchings and Coverings
In complete graphs, a matching is an edge subset with no shared vertices. The size of a maximum matching in K_n is \lfloor n/2 \rfloor, as edges can pair up vertices until at most one remains unpaired if n is odd.[26] When n = 2m is even, perfect matchings exist that saturate all vertices, and their number is given by the double factorial (2m-1)!! = (2m-1)(2m-3)\cdots 3 \cdot 1, which counts the ways to pair vertices sequentially: the first vertex has $2m-1 choices, the next unpaired has $2m-3, and so on.[26] This sequence is also known as the telephone numbers and appears as OEIS A000085. An edge cover in K_n is an edge subset incident to every vertex. By Gallai's identity, the minimum edge cover size \rho(K_n) equals n - \nu(K_n) = n - \lfloor n/2 \rfloor, since K_n has no isolated vertices.[26] For even n = 2m, this is m, achieved by any perfect matching. For odd n = 2m+1, it is m+1, obtained by a maximum matching of m edges plus one additional edge to cover the unpaired vertex. A vertex cover in K_n is a vertex subset incident to every edge. The independence number \alpha(K_n) = [1](/page/1), as no two vertices form an independent set. By the complementary Gallai identity, the minimum vertex cover size \tau(K_n) = n - \alpha(K_n) = n-[1](/page/1), achieved by excluding any single vertex, whose incident edges are covered by the others.[26] Excluding two or more leaves an uncovered edge between them.Geometry and Embeddings
Planarity and Crossing Numbers
A complete graph K_n is planar if and only if n \leq 4, as K_5 is the smallest non-planar complete graph and contains no proper subdivisions beyond itself that alter this property.[27] By Kuratowski's theorem, a graph is non-planar if it contains a subdivision of K_5 or K_{3,3} as a subgraph; since K_5 is itself one of these forbidden subgraphs, all K_n for n \geq 5 are non-planar for the same reason. For n > 5, K_n embeds K_5 directly as an induced subgraph, reinforcing non-planarity without requiring subdivisions.[28] The crossing number \operatorname{cr}(K_n), defined as the minimum number of edge crossings in any drawing of K_n in the plane, is zero for n \leq 4 due to planarity. For n \geq 5, exact values are known for small n: \operatorname{cr}(K_5) = 1, achieved by drawing four vertices in convex position with the fifth inside and edges crossing once; \operatorname{cr}(K_6) = 3, obtained by adding a sixth vertex to the K_5 drawing with minimal additional crossings.[29] These values form the beginning of the sequence for \operatorname{cr}(K_n), cataloged as A000241 in the OEIS, with further exact determinations up to n=27 as of 2024.) The Zarankiewicz problem, which seeks the maximum edges in a bipartite graph avoiding complete bipartite subgraphs K_{s,t}, connects to crossing numbers of complete graphs via upper-bound constructions for \operatorname{cr}(K_n). Specifically, Zarankiewicz's conjecture posits that \operatorname{cr}(K_{m,n}) = \left\lfloor \frac{m}{2} \right\rfloor \left\lfloor \frac{m-1}{2} \right\rfloor \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor for complete bipartite graphs, providing a benchmark for crossings in bipartite drawings.[30] To bound \operatorname{cr}(K_n), a standard construction partitions the n vertices into two nearly equal sets of sizes \lfloor n/2 \rfloor and \lceil n/2 \rceil, drawn on two concentric circles or layers to minimize total crossings, yielding \operatorname{cr}(K_n) \leq Z(n), where Z(n) is the conjectured value.[31] This yields the conjectured formula for \operatorname{cr}(K_n) as \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor (Hill's conjecture, referenced by Guy), exact for n \leq 27 and asymptotically \sim \frac{1}{64} n^4.[32][29]Topological Properties
The complete graph K_n serves as the 1-skeleton of the (n-1)-simplex, where the vertices correspond to the simplex's vertices and the edges connect every pair, embedding the graph in (n-1)-dimensional Euclidean space without crossings.[33] This realization highlights the complete graph's role in simplicial geometry, as the higher-dimensional faces of the simplex fill in the combinatorial structure beyond the mere edges.[33] A notable embedding on a non-spherical surface occurs with K_7, whose 1-skeleton forms the Császár polyhedron, a toroidal polyhedron with 7 vertices, 21 edges, and 14 triangular faces that realizes the complete graph on a torus without self-intersections.[34] Discovered by Ákos Császár in 1949, this polyhedron demonstrates that K_7 can be embedded on a surface of genus 1, providing a polyhedral model for the torus's triangulation with the minimal number of vertices.[34] In three-dimensional space, embeddings of complete graphs exhibit intrinsic topological complexities, as established by the Conway-Gordon theorem. Specifically, every embedding of K_6 in \mathbb{R}^3 contains a pair of disjoint cycles that form a non-trivially linked 2-component link, making K_6 intrinsically linked.[35] Similarly, every embedding of K_7 in \mathbb{R}^3 includes a knotted Hamiltonian cycle, rendering K_7 intrinsically knotted.[35] These results, proved using algebraic invariants like linking numbers modulo 2, underscore the unavoidable knotting and linking in spatial realizations of small complete graphs.[35]Examples and Applications
Small Complete Graphs
The complete graph K_1 consists of a single vertex with no edges, representing the simplest possible graph and serving as the trivial case in graph theory.[1] It has zero edges and is often denoted as the singleton graph. Visually, it appears as an isolated point. The complete graph K_2 comprises two vertices connected by a single edge, forming the basic building block for more complex graphs.[1] With exactly one edge, it resembles a straight line segment between two points and is the smallest non-trivial complete graph. K_3, known as the triangle graph, features three vertices where each pair is joined by an edge, resulting in three edges total and forming a closed triangular shape.[1] This graph is isomorphic to the cycle graph C_3, emphasizing its cyclic structure without additional connections. The complete graph K_4 includes four vertices, each connected to every other, yielding six edges and embodying the tetrahedral graph, which corresponds to the skeleton of a regular tetrahedron.[1][36] It is also isomorphic to the wheel graph W_4, though distinct from complete bipartite graphs like the utility graph K_{3,3}, which connects vertices across two disjoint sets without intra-set edges.[37] Visually, K_4 can be drawn as a tetrahedron with vertices at the corners and edges along the faces, remaining planar unlike larger complete graphs starting from K_5. The number of edges in a complete graph K_n grows quadratically as \frac{n(n-1)}{2}, providing a quick reference for small instances as shown below.[1]| n | Edges in K_n |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 3 |
| 4 | 6 |
| 5 | 10 |
| 6 | 15 |
| 7 | 21 |
| 8 | 28 |
| 9 | 36 |
| 10 | 45 |
| 11 | 55 |
| 12 | 66 |