Worldlex Wiki On fait généralement remonter la théorie des graphes aux travaux de Leonhard Euler sur les Sept Ponts de Königsberg en 1736. Cependant, des représentations de graphes complets, dont les sommets sont placés aux points d'un polygone régulier , apparaissent déjà au XIIIe siècle, dans les travaux de Ramon Llull . Ce type de représentation est parfois appelé « rose mystique » .
Kazimierz Kuratowski à la théorie des graphes.nombre triangulaire ) et est un graphe régulier de degré clique maximale . Il est maximalement connexe car la seule coupe de sommets qui le déconnecte est l'ensemble complet des sommets. Le graphe complémentaire d'un graphe complet est le graphe vide .
Si l'on attribue une orientation à chaque arête d'un graphe complet , le graphe orienté résultant est appelé un tournoi .
les chemins distincts entre une paire de sommets spécifique dans
Géométrie et topologie
Un graphe complet à graphe des arêtes d'un simplexe de dimension , K₄ tétraèdre , etc. Le polyèdre de Császár , un polyèdre non convexe muni de la topologie d'un tore , a pour squelette le graphe complet polytope voisin en quatre dimensions ou plus possède également un squelette complet.
planaires . Cependant, toute représentation planaire d'un graphe complet à cinq sommets ou plus contient nécessairement une intersection, et le graphe complet non planaire le théorème de Kuratowski , un graphe est planaire si et seulement s'il ne contient ni graphe biparti complet même résultat est valable pour les mineurs de graphes à la place des subdivisions. Appartenant à la famille de Petersen , mineur interdit pour l'immersion sans entrelacement .Autrement dit, et comme l'ont démontré Conway et Gordon cycle hamiltonien qui est plongé dans l'espace comme un nœud non trivial .
Exemples
Les graphes complets à sommets, pour un nombre de sommets compris entre 1 et 12, sont présentés ci-dessous avec le nombre d'arêtes :
 |  |  | |
 |  |  | |
 |  |  |