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).

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, appeared already in the 13th century, in the work of Ramon Llull. [1] Such a drawing is sometimes referred to as a mystic rose. [2]

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, [3] 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. [4]

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. [5] Ringel's conjecture asks if the complete graph K2n+1 can be decomposed into copies of any tree with n edges. [6] This is known to be true for sufficiently large n. [7] [8]

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. [9] The number of perfect matchings of the complete graph Kn (with n even) is given by the double factorial (n  1)!!. [10]

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. [11] 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. 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. [13] In other words, and as Conway and Gordon [14] 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 n vertices, for n 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.

Three utilities problem Mathematical problem

The classical mathematical puzzle known as the three utilities problem; the three cottages problem or sometimes water, gas and electricity can be stated as follows:

Suppose there are three cottages on a plane and each needs to be connected to the water, gas, and electricity companies. Without using a third dimension or sending any of the connections through another company or cottage, is there a way to make all nine connections without any of the lines crossing each other?

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Complete bipartite graph Bipartite graph where every vertex of the first set is connected to every vertex of the second 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.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G 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.

In mathematics, 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).

Császár polyhedron

In geometry, the Császár polyhedron is a nonconvex toroidal polyhedron with 14 triangular faces.

Crossing number (graph theory)

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 (simple) 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. Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."

Turáns brick factory problem Problem of minimizing crossings in complete bipartite graphs

In the mathematics of graph drawing, Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

Polyhedral graph

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.

Herschel graph

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel.

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.

Petersen family

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.

Apex graph

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.

1-planar graph

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.

Kelmans–Seymour conjecture

In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof has been announced but not yet published.

References

  1. 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 .
  2. Mystic Rose, nrich.maths.org, retrieved 23 January 2012.
  3. Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436, ISBN   0387941150 .
  4. Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p.  154, ISBN   9780201308150 .
  5. 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.
  6. Ringel, G. (1963). Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice.
  7. Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020-01-08). "A proof of Ringel's Conjecture". arXiv: 2001.02665 [math.CO].
  8. Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts". Quanta Magazine. Retrieved 2020-02-20.
  9. 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 .
  10. Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv: 0906.1317 , Bibcode:2009arXiv0906.1317C .
  11. Oswin Aichholzer. "Rectilinear Crossing Number project". Archived from the original on 2007-04-30.
  12. Ákos Császár, A Polyhedron Without Diagonals. Archived 2017-09-18 at the Wayback Machine , Bolyai Institute, University of Szeged, 1949
  13. 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 .
  14. Conway, J. H.; Cameron Gordon (1983). "Knots and Links in Spatial Graphs". J. Graph Th. 7 (4): 445–453. doi:10.1002/jgt.3190070410.