Complete graph

Last updated
Complete graph
Complete graph K7.svg
K7, a complete graph with 7 vertices
Vertices n
Edges
Radius
Diameter
Girth
Automorphisms n! (S n)
Chromatic number n
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]

Contents

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 n vertices is denoted by Kn. Some sources claim that the letter K in this notation stands for the German word komplett, [4] but the German name for a complete graph, vollständiger Graph, does not contain the letter K, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. [5]

Kn has n(n – 1)/2 edges (a triangular number), and 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.

Kn can be decomposed into n trees Ti such that Ti has i vertices. [6] Ringel's conjecture asks if the complete graph K2n+1 can be decomposed into copies of any tree with n edges. [7] This is known to be true for sufficiently large n. [8] [9]

The number of all distinct paths between a specific pair of vertices in Kn+2 is given [10] by

where e refers to Euler's constant, and

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, ... (sequence A000085 in the OEIS ).

These numbers give the largest possible value of the Hosoya index for an n-vertex graph. [11] The number of perfect matchings of the complete graph Kn (with n even) is given by the double factorial (n – 1)!!. [12]

The crossing numbers up to K27 are known, with K28 requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project. [13] Rectilinear Crossing numbers for Kn 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, ... (sequence A014540 in the OEIS ).

Geometry and topology

Interactive Csaszar polyhedron model with vertices representing nodes. In the SVG image, move the mouse to rotate it. Csaszar polyhedron 3D model.svg
Interactive Csaszar polyhedron model with vertices representing nodes. In the SVG image, move the mouse to rotate it.

A complete graph with n nodes represents the edges of an (n – 1)-simplex. Geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K7 as its skeleton. [15] Every neighborly polytope in four or more dimensions also has a complete skeleton.

K1 through K4 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 K5 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 K5 nor the complete bipartite graph K3,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, K6 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 K6 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 K7 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.

Examples

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

K1: 0K2: 1K3: 3K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10K6: 15K7: 21K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36K10: 45K11: 55K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

See also

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Three utilities problem</span> Mathematical puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete.

<span class="mw-page-title-main">Complete bipartite graph</span> Bipartite graph where each node of 1st set is linked to all nodes of 2nd set

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Geometric graph theory</span> Subfield of graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs". Geometric graphs are also known as spatial networks.

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

<i>k</i>-vertex-connected graph Graph which remains connected when k or fewer nodes removed

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

<span class="mw-page-title-main">Crossing number (graph theory)</span> Fewest edge crossings in drawing of a graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Polyhedral graph</span> Graph made from vertices and edges of a convex polyhedron

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

<span class="mw-page-title-main">Herschel graph</span> Bipartite non-Hamiltonian polyhedral graph

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

<span class="mw-page-title-main">Petersen family</span> Family of 7 undirected graphs

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.

References

  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.
  4. Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436, ISBN   0387941150 .
  5. Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p.  154, ISBN   9780201308150 .
  6. Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). "Optimal packings of bounded degree trees" (PDF). Journal of the European Mathematical Society . 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN   1435-9855. S2CID   119315954. Archived (PDF) from the original on 2020-03-09. Retrieved 2020-03-09.
  7. Ringel, G. (1963). Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice.
  8. Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). "A proof of Ringel's Conjecture". Geometric and Functional Analysis. 31 (3): 663–720. arXiv: 2001.02665 . doi: 10.1007/s00039-021-00576-2 .
  9. Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts". Quanta Magazine. Archived from the original on 2020-02-20. Retrieved 2020-02-20.
  10. Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123126, 2004.
  11. Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology , 12 (7): 1004–1013, CiteSeerX   10.1.1.379.8693 , doi:10.1089/cmb.2005.12.1004, PMID   16201918, archived (PDF) from the original on 2017-09-21, retrieved 2012-03-29.
  12. Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv: 0906.1317 , Bibcode:2009arXiv0906.1317C .
  13. Oswin Aichholzer. "Rectilinear Crossing Number project". Archived from the original on 2007-04-30.
  14. Ákos Császár, A Polyhedron Without Diagonals. Archived 2017-09-18 at the Wayback Machine , Bolyai Institute, University of Szeged, 1949
  15. Gardner, Martin (1988), Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, p. 140, Bibcode:1988ttom.book.....G, ISBN   0-7167-1924-X
  16. Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv: math/9301216 , doi:10.1090/S0273-0979-1993-00335-5, MR   1164063, S2CID   1110662 .
  17. Conway, J. H.; Cameron Gordon (1983). "Knots and Links in Spatial Graphs". Journal of Graph Theory . 7 (4): 445–453. doi:10.1002/jgt.3190070410.