# 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

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()