Complete Graphs

Understanding Complete Graphs

• A complete graph is a specific type of graph in which every distinct pair of vertices is connected by an edge.
• It is denoted as K_n, where n indicates the number of vertices in the graph.
• One crucial property of complete graphs is that they are always connected, meaning there is a path from every vertex to every other vertex.
• Complete graphs are also simple graphs, as they do not have loops or multiple edges between the same pair of vertices.

Properties of Complete Graphs

• The total number of edges in a complete graph K_n is given by the formula n(n - 1)/2, which is derived from the fact that each vertex is connected to every other vertex.
• In a complete graph, the degree of each vertex is equal to n - 1, where n is the number of vertices in the graph.
• A complete graph is Hamiltonian, meaning there is a cycle that visits each vertex in the graph exactly once.
• Furthermore, a complete graph has as many Hamiltonian cycles as (n-1)!, divided by 2, for n greater than 2.

Complete Bipartite Graphs

• A complete bipartite graph, denoted as K_(m,n), is a specific type of complete graph where its vertex set can be partitioned into two disjoint subsets, with no edges within subsets.
• In a complete bipartite graph, every vertex in the first subset is connected to every vertex in the second subset.
• The number of edges in a complete bipartite graph K_(m,n) can be calculated using the formula m*n, where m and n are the orders of the two subsets of vertices respectively.
• A complete bipartite graph is Hamiltonian if both m and n are greater than or equal to 2.