A complete graph is a graph where every pair of distinct vertices is joined by an edge, so every vertex is connected to every other vertex.

Quick Scoop

Simple definition

  • A complete graph is one where nothing is “missing”: if you pick any two different vertices, there is an edge between them.
  • In symbols, the complete graph on nnn vertices is written as KnK_nKn​.

Small examples

  • K1K_1K1​: just a single vertex, no edges.
  • K2K_2K2​: two vertices with one edge between them.
  • K3K_3K3​: a triangle (three vertices, each connected to the other two).
  • K4K_4K4​: four vertices, every vertex joined to the other three; it looks like a tetrahedron drawn on paper.

Key properties (fast facts)

  • Number of vertices: nnn.
  • Degree of each vertex: n−1n-1n−1 (it connects to all the others).
  • Number of edges: n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ in an undirected complete graph.
  • Always connected : there is a path between any two vertices.
  • For n≥3n\ge 3n≥3, KnK_nKn​ is Hamiltonian : there is a cycle that visits every vertex exactly once and returns to the start.

How to recognize one

To check if a graph with nnn vertices is complete:

  1. Make sure every vertex has degree n−1n-1n−1 (each touches all others).
  2. Count edges and see if there are n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ edges.
  3. Verify there is an edge between every pair of distinct vertices; if even one pair is missing, it is not complete.

Why it matters (intuition)

  • Think of a complete graph as a “everyone-knows-everyone” social network: each person (vertex) is directly connected to every other person (edge).
  • In graph theory and algorithms, complete graphs often represent “maximally dense” connectivity and provide extreme test cases for routing, coloring, and network design problems.

In short, when you hear “complete graph,” think “all possible edges are present, nothing left out.”

Information gathered from public forums or data available on the internet and portrayed here.