Complete graph

Complete graph
K7, a complete graph with 7 vertices
Verticesn
Edges
Radius
Diameter
Girth
Automorphismsn! (Sn)
Chromatic numbern
Chromatic index
  • n if n is odd
  • n − 1 if n is even
Spectrum
Properties
NotationKn
Table of graphs and parameters

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. A complete digraph is a directed 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 with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull.[2] Such a drawing is sometimes referred to as a mystic rose.[3]

  1. ^ Bang-Jensen, Jørgen; Gutin, Gregory (2018), "Basic Terminology, Notation and Results", in Bang-Jensen, Jørgen; Gutin, Gregory (eds.), Classes of Directed Graphs, Springer Monographs in Mathematics, Springer International Publishing, pp. 1–34, doi:10.1007/978-3-319-71840-8_1; see p. 17
  2. ^ Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 978-0191630620.
  3. ^ Mystic Rose, nrich.maths.org, retrieved 23 January 2012.