Graphs and Networks: Complete Graphs

Graphs and Networks: Complete Graphs

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.