Course contentsShow
← Computer Science
Lesson 688 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Complete Graphs

Exploring graphs where every pair of vertices is connected and their combinatorial properties.

Complete Graphs

What You'll Learn

You'll discover what makes a graph "complete" and explore the fundamental combinatorial properties that define these maximally-connected structures.

What is a Complete Graph?

A complete graph is a simple graph where every single pair of distinct vertices is connected by exactly one edge. In other words, if you have n vertices, every vertex connects directly to every other vertex—no exceptions.

Think of it like a dinner party where everyone has personally met and shaken hands with everyone else. No strangers, no missing connections.

Notation and Structure

Complete graphs are denoted as K_n, where n is the number of vertices:

  • K₃: A triangle (3 vertices, 3 edges)
  • K₄: Four vertices where each connects to the other three (6 edges)
  • K₅: Five vertices, all interconnected (10 edges)

Notice that complete graphs are always simple graphs—no self-loops and no multiple edges between the same pair of vertices.

The Edge Count Formula

Here's the key combinatorial property: How many edges does K_n have?

Since each vertex connects to every other vertex exactly once, we're choosing 2 vertices from n vertices:

Number of edges = n(n-1)/2

  • K₃: 3(2)/2 = 3 edges
  • K₄: 4(3)/2 = 6 edges
  • K₅: 5(4)/2 = 10 edges
  • K₁₀₀: 100(99)/2 = 4,950 edges

This quadratic growth means complete graphs become extremely dense very quickly. In adjacency matrix representation, K_n is nearly all 1s (except the diagonal).

Properties

  • Every vertex has degree n-1 (connected to all others)
  • Always connected (you can reach any vertex from any other)
  • Contains every possible simple subgraph on n vertices

Key Takeaway: A complete graph K_n connects every pair of its n vertices with exactly one edge, resulting in n(n-1)/2 total edges—the maximum possible for a simple graph.