# Complete Graphs

## Definition and Characteristics

• 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.

## Special Types of Complete Graphs

• 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.

## Graph Properties

• 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.

## Complete Graph Theorems

• 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.