Complete graph

The full graph up to . ${\displaystyle K_{1}}$ ${\displaystyle K_{5}}$

A complete graph is a term from graph theory and describes a simple graph in which every node is connected to every other node by an edge . The complete graph with nodes is uniquely determined (except for isomorphism ) and is denoted by. ${\displaystyle n}$ ${\displaystyle K_{n}}$

If the set of nodes of the complete graph , then the set of edges is exactly the set of edges between pairs of different nodes . ${\displaystyle V=\{v_{1},\dotsc ,v_{n}\}}$ ${\displaystyle K_{n}}$ ${\displaystyle E}$ ${\displaystyle E=\{\{v_{i},v_{j}\}:1\leq i<j\leq n\}}$

A complete graph is also its maximal clique .

properties

The complete graphs to are planar . All other complete graphs are not planar according to Kuratowski's theorem , since they contain them as a subgraph. ${\displaystyle K_{1}}$ ${\displaystyle K_{4}}$ ${\displaystyle K_{5}}$

The number of edges of the complete graph corresponds to the triangle number ${\displaystyle K_{n}}$

${\displaystyle \Delta _{n-1}={n \choose 2}={\frac {n(n-1)}{2}}}$.

The complete graph is a - regular graph : each node has neighbors . Because of this, every node coloring of the graph has colors. Furthermore, it follows that the complete graphs are Eulerian for odd and not for even . ${\displaystyle K_{n}}$ ${\displaystyle (n-1)}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Complete graphs are for Hamiltonian graphs . The complete graph contains different Hamilton circles . ${\displaystyle n>2}$ ${\displaystyle K_{n}}$ ${\displaystyle {\tfrac {1}{2}}(n-1)!}$

generalization

The idea of ​​the complete graph can be transferred to -partite graphs . These are complete if every node of a partition is connected to all nodes of all other partitions. The complete multipartite graph with partition sets containing nodes is called . ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle n_{1},\dotsc ,n_{p}}$ ${\displaystyle K_{n_{1},\dotsc ,n_{p}}}$

If you provide a complete graph with an orientation, you get a tournament graph .

software

Using free Python - Library NetworkX to complete graphs can be generated. Example:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.complete_graph(15)

nx.draw_circular(G, with_labels=True, font_weight='bold')
plt.show()

literature

• Lutz Volkmann: Foundations of the graph theory. Springer, Vienna 1996, ISBN 3-211-82774-9 ; newer version: graphs at all corners and edges (PDF; 3.7 MB)

Web links

• Eric W. Weisstein : Complete Graph . In: MathWorld (English).