**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Complete graph

Summary

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).
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. Such a drawing is sometimes referred to as a mystic rose.
The complete graph on n vertices is denoted by K_n. Some sources claim that the letter K in this notation stands for the German word komplett, 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.
K_n 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.
K_n can be decomposed into n trees T_i such that T_i has i vertices. Ringel's conjecture asks if the complete graph K_2n+1 can be decomposed into copies of any tree with n edges. This is known to be true for sufficiently large n.
The number of all distinct paths between a specific pair of vertices in K_n+2 is given 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, ... .
These numbers give the largest possible value of the Hosoya index for an n-vertex graph.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (6)

Related people (1)

Related courses (15)

Related concepts (90)

Related lectures (65)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

ME-303: Microinformatique (pour GM)

Comprendre les microcontrôleurs et apprendre à les mettre en oeuvre, en particulier pour la commande de systèmes mécaniques.

MATH-467: Probabilistic methods in combinatorics

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

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

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Markov Chains and ApplicationsCOM-516: Markov chains and algorithmic applications

Explores Markov chains, Ising Model, Metropolis algorithm, and Glauber dynamics.

Ramsey Theory: Alterations and ColoringsMATH-467: Probabilistic methods in combinatorics

Explores Ramsey theory, alterations, colorings in graphs, monochromatic matchings, and the significance of large cliques.

Subgraphs vs Induced Subgraphs

Distinguishes between subgraphs and induced subgraphs in graph theory, illustrating the construction of minimal spanning trees.

An ordered graph is a pair G = (G,

In this thesis, we study the homotopical relations of 2-categories, double categories, and their infinity-analogues. For this, we construct homotopy theories for the objects of interest, and show that

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is