Complete graph
From Free net encyclopedia
In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of vertices. The complete graph on <math>n</math> vertices has <math>n</math> vertices and <math>n(n-1)/2</math> edges, and is denoted by <math>K_n</math>. It is a regular graph of degree <math>n-1</math>. All complete graphs are their own cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices
A planar graph cannot contain <math>K_5</math> (or the complete bipartite graph <math>K_{3,3}</math>) as a minor. Since <math>K_n</math> includes <math>K_{n-1}</math>, no complete graph <math>K_n</math> with <math>n</math> greater than or equal to 5 is planar.
Complete graphs on <math>n</math> vertices, for <math>n</math> between 1 and 8, are shown below:
 <math>K_1</math> |
 <math>K_2</math> |
 <math>K_3</math> |
 <math>K_4</math> |
 <math>K_5</math> |
 <math>K_6</math> |
 <math>K_7</math> |
 <math>K_8</math> |
de:Vollständiger Graph fr:Graphe complet ko:완전 그래프 it:Grafo completo lt:Pilnasis grafas pl:Graf pełny pt:Grafo completo sl:Polni graf th:กราฟบริบูรณ์ vi:Đồ thị đầy đủ zh:完全圖