Complete graph

A complete graph is a term from graph theory and refers to a simple graph in which all nodes are connected to each over an edge. The complete graph with node is uniquely determined ( up to isomorphism ) and is denoted by.

If the node-set of, so is the edge set E consists of exactly the set of edges between pairs of different nodes.

A complete graph is also its maximum clique.

Properties

The complete graph to be planar. All other complete graphs are not planar by the theorem of Kuratowski, as they contain as a subgraph.

The number of edges of the complete graph corresponds to the triangular number

The complete graph is one - regular graph: each node has neighbors. Because of this, each node of the graph coloring colors. Furthermore, it follows that the complete graph of odd Euler tour are and just do not.

Complete graphs are for Hamiltonian graphs. The complete graph it contains several Hamilton circuits.

Generalization

The idea of the complete graph can be applied to - partite graph. These are complete if each node of a partition is connected to all nodes of all other partitions. The complete multipartite graph with partite sets containing nodes, denoted by one.

Provides you a complete graph with an orientation, one obtains a tournament graph.