Complete Graphs

Graph Theory · Axiom Academy

Understanding the maximally connected graphs in graph theory 1. Definition of Complete Graph K n Definition: A complete graph K n is a simple graph with n vertices where every pair of distinct vertices is connected by exactly one edge. Watch as we build complete graphs K 3 , K 4 , and K 5 step by step, showing how every vertex connects to every other vertex. Since each vertex must connect to every other vertex, we can derive a formula for the number of edges. With n vertices, each vertex connects to n-1 other vertices. However, this counts each edge twice (once from each endpoint), so we divide by 2: In a complete graph K n , every vertex has the same degree. Since each vertex connects to all other vertices: 4. Complete Bipartite Graphs K m,n Definition: A complete bipartite graph K m,n has two disjoint sets of vertices with m and n vertices respectively, where every vertex in one set connects to every vertex in the other set, but no edges exist within the same set. Common examples include K 3,3 (the utility graph) and K 2,3 . 5. Properties and Applications K n is the unique simple graph on n vertices with maximum edge count K n has a clique number of n (it is itself a maximum clique) K n is both vertex-transitive and edge-transitive The complement of K n is the empty graph on n vertices Network Design: Modeling fully connected networks where every node can directly communicate Scheduling: K n represents all possible pairings in round-robin tournaments

This is the written version of the interactive lesson above. See the full Graph Theory course.