All Topics  
Complete graph

 

 
   Email Print
   Bookmark   Link
 

 

Complete graph
 
 
  Topics Complete graph Topic Home

In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, a complete graph is a simple graph in which every pair of distinct vertices
Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs ....
 is connected by an edge. The complete graph on n vertices has n vertices and n(n-1)/2 edges, and is denoted by . It is a regular graph
Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same Degree or valency....
 of degree
Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
 . All complete graphs are their own clique
Clique (graph theory)

In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....
s. They are maximally connected
Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems....
 as the only vertex cut which disconnects the graph is the complete set of vertices.

A complete graph with n nodes represents the edges of an (n-1)-simplex
Simplex

In geometry, a simplex or n-simplex is an n-dimensional analogue of a triangle. Specifically, a simplex is the convex hull of a set of affine transformation Point s in some Euclidean space of dimension n or higher ....
.






Discussion
Ask a question about 'Complete graph'
Start a new discussion about 'Complete graph'
Answer questions from other users
Full Discussion Forum



Recent Posts

A program that determines whether a graph is a bipartite qraph.if it is a bipartite graph, the progr...
Assignment








Encyclopedia


In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, a complete graph is a simple graph in which every pair of distinct vertices
Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs ....
 is connected by an edge. The complete graph on n vertices has n vertices and n(n-1)/2 edges, and is denoted by . It is a regular graph
Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same Degree or valency....
 of degree
Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
 . All complete graphs are their own clique
Clique (graph theory)

In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....
s. They are maximally connected
Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems....
 as the only vertex cut which disconnects the graph is the complete set of vertices.

A complete graph with n nodes represents the edges of an (n-1)-simplex
Simplex

In geometry, a simplex or n-simplex is an n-dimensional analogue of a triangle. Specifically, a simplex is the convex hull of a set of affine transformation Point s in some Euclidean space of dimension n or higher ....
. Geometrically relates to a triangle
Triangle

A triangle is one of the basic shapes of geometry: a polygon with three corners or wikt:vertex and three sides or edges which are line segments....
, a tetrahedron
Tetrahedron

A tetrahedron is a polyhedron composed of four triangle faces, three of which meet at each vertex . A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids....
, a pentachoron
Pentachoron

In geometry, the pentachoron is a fourth dimension object bounded by 5 tetrahedron. It is also known as the 5-cell, pentatope, or hyperpyramid....
, etc.

through are all planar. Kuratowski's theorem says that a planar graph
Planar graph

In graph theory, a planar graph is a graph which can be graph embedding in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints....
 cannot contain (or the complete bipartite graph
Complete bipartite graph

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....
 ) as a minor
Minor (graph theory)

In graph theory, a graph H is called a minor of the graph G if H is Graph isomorphism to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
. Since includes , no complete graph with n greater than or equal to 5 is planar.

Since a complete graph contains all n(n-1)/2 possible edges, it gives a quadratic upper bound
Upper bound

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S....
 on the number of connections in large connected systems like social and computer networks.

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

Complete Graph K1
Complete Graph K2
Complete Graph K3
Complete Graph K4
Complete Graph K5
Complete Graph K6
Complete Graph K7
Complete Graph K8


See also

  • Cycle graph
    Cycle graph

    In graph theory, a cycle graph is a graph that consists of a single path , or in other words, some number of vertices connected in a closed chain....
  • Path graph
    Path graph

    In the Mathematics field of graph theory, a path graph is a particularly simple example of a tree , namely one which is not branched at all, that is, contains only nodes of degree two and one....
  • Null graph
    Null graph

    The null graph or the empty graph is either the graph with no vertices and no edges, or any graph with no edges.The null graph is the initial object in the category of graphs, according to some definitions of a category of graphs....
  • Clique (graph theory)
    Clique (graph theory)

    In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....


External links


  • Counting Paths and Cycles in Complete Graphs. Results are available or