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.