Complete graph

From testwiki
Jump to navigation Jump to search

Template:Short description Template:Infobox graph 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]

Properties

The complete graph on Template:Mvar vertices is denoted by Template:Mvar. Some sources claim that the letter Template:Mvar in this notation stands for the German word Template:Lang,[4] but the German name for a complete graph, Template:Lang, does not contain the letter Template:Mvar, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.[5]

Template:Mvar has Template:Math edges (a triangular number), and is a regular graph of degree Template:Math. 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.

Template:Mvar can be decomposed into Template:Mvar trees Template:Mvar such that Template:Mvar has Template:Mvar vertices.[6] Ringel's conjecture asks if the complete graph Template:Math can be decomposed into copies of any tree with Template:Mvar edges.[7] This is known to be true for sufficiently large Template:Mvar.[8][9]

The number of all distinct paths between a specific pair of vertices in Template:Math is given[10] by

wn+2=n!en=⌊en!⌋,

where Template:Mvar refers to Euler's constant, and

en=∑k=0n1k!.

The number of matchings of the complete graphs are given by the telephone numbers

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... Template:OEIS.

These numbers give the largest possible value of the Hosoya index for an Template:Mvar-vertex graph.[11] The number of perfect matchings of the complete graph Template:Mvar (with Template:Mvar even) is given by the double factorial Template:Math.[12]

The crossing numbers up to Template:Math are known, with Template:Math requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.[13] Rectilinear Crossing numbers for Template:Mvar 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, ... Template:OEIS.

Geometry and topology

Interactive Csaszar polyhedron model with vertices representing nodes. In the SVG image, move the mouse to rotate it.[14]

A complete graph with Template:Mvar nodes represents the edges of an Template:Math-simplex. Geometrically Template:Math forms the edge set of a triangle, Template:Math a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph Template:Math as its skeleton.[15] Every neighborly polytope in four or more dimensions also has a complete skeleton.

Template:Math through Template:Math 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 Template:Math 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 Template:Math nor the complete bipartite graph Template:Math 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, Template:Math plays a similar role as one of the forbidden minors for linkless embedding.[16] In other words, and as Conway and Gordon[17] proved, every embedding of Template:Math 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 of Template:Math contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.

Examples

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

Template:Math Template:Math Template:Math Template:Math
File:Complete graph K2.svg File:Complete graph K3.svg
Template:Math Template:Math Template:Math Template:Math
File:5-simplex graph.svg
Template:Math Template:Math Template:Math Template:Math
Error creating thumbnail: File:10-simplex graph.svg Error creating thumbnail:

See also

References

Template:Reflist

Template:Commons Template:Wiktionary

Template:Authority control

  1. ↑ Template:Citation; see p. 17
  2. ↑ Template:Citation.
  3. ↑ Template:Citation.
  4. ↑ Template:Citation.
  5. ↑ Template:Citation.
  6. ↑ Template:Cite journal
  7. ↑ Template:Cite conference
  8. ↑ Template:Cite journal
  9. ↑ Template:Cite web
  10. ↑ Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
  11. ↑ Template:Citation.
  12. ↑ Template:Citation.
  13. ↑ Template:Cite web
  14. ↑ Ákos Császár, A Polyhedron Without Diagonals. Template:Webarchive, Bolyai Institute, University of Szeged, 1949
  15. ↑ Template:Citation
  16. ↑ Template:Citation.
  17. ↑ Template:Cite journal
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Complete_graph&oldid=2423"