Graphs and Networks: Complete Graphs

Complete Graphs

A Complete Graph is a unique type of graph in which every pair of distinct vertices is connected by precisely one edge.
A complete graph with ‘n’ vertices is denoted by K_n.
In a complete graph, each vertex has a degree of ‘n-1’, indicating that it is directly connected to every other vertex.

Complete Bipartite Graphs have their vertex set partitioned into two distinct sets, and there exists an edge between every pair of vertices from different sets.
A complete bipartite graph with partitions containing ‘m’ and ‘n’ vertices is denoted by K_{m,n}.
The Thomassen Graphs are a family of complete bipartite graphs that are also Hamiltonian.
A Complete Digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges in both directions.

The complement of complete graph K_n is an empty graph with n vertices, named E_n.
A cycle exists in a complete graph when ‘n’ is 3 or greater, making them all cyclical.
All complete graphs are planar when ‘n’ is less than or equal to 4. By contrast, K_n is non-planar when ‘n’ is 5 or more.
Due to their regular structure, complete graphs are commonly used in graphical representations of networks, notably in the study of social networks and communication networks.

According to Turán’s theorem, the complete graph K_n contains the most edges a graph can have without containing a clique of size ‘r+1’.
The Handshaking Lemma states that in any graph, the sum of the degrees of all the vertices is equal to twice the number of edges. For a complete graph, this sums up to ‘n*(n-1)’.
Mantel’s Theorem provides a threshold for when the largest possible graph avoiding complete graph K_3 (triangle) becomes a complete bipartite graph.