Complete Graphs: The Most Connected Graphs

Introduction

Imagine a social network where everyone knows everyone else - no exceptions. In graph theory, this is precisely what a complete graph represents: the ultimate in connectivity, where every possible edge exists.

Complete graphs are among the most important structures in graph theory. They serve as:
- Building blocks for more complex graphs
- Benchmarks for maximum edge density
- Test cases for graph algorithms
- Models for fully-connected systems

In this comprehensive guide, we’ll explore what makes complete graphs special, derive their fundamental properties, and see why they’re called “complete.”

Definition and Notation

What is a Complete Graph?

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by exactly one edge.

Formal Definition: A simple graph \(G = (V, E)\) is complete if for all vertices \(u, v \in V\) where \(u \neq v\), the edge \((u, v) \in E\).

Standard Notation

Complete graphs are denoted by \(K_n\), where:
- \(K\) stands for “komplett” (German for “complete”)
- \(n\) represents the number of vertices (the order of the graph)

For example:
- \(K_1\): A single vertex
- \(K_4\): Four vertices, all connected
- \(K_{10}\): Ten vertices with every possible edge

Fundamental Properties

Complete graphs have several remarkable properties that make them unique.

Property 1: Maximum Edge Count

A complete graph \(K_n\) has the maximum possible number of edges for a simple graph of order \(n\).

Edge Formula: \(|E| = \frac{n(n-1)}{2}\)

Why this formula? Let’s derive it:
1. Each vertex must connect to \(n - 1\) other vertices
2. If we sum all connections: \(n \times (n - 1)\)
3. But this counts each edge twice (once from each endpoint)
4. Therefore: \(|E| = \frac{n(n-1)}{2}\)

Alternative derivation using combinations:
- We need to choose 2 vertices from \(n\) vertices to form an edge
- Number of ways = \(\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}\)

Property 2: Regular Graph Structure

Every complete graph \(K_n\) is a \((n-1)\)-regular graph.

Proof:
- By definition, each vertex in \(K_n\) connects to every other vertex
- There are \(n\) total vertices
- Therefore, each vertex has degree \(n - 1\)
- Since all vertices have the same degree, \(K_n\) is \((n-1)\)-regular

This connects complete graphs to our previous discussion of regular graphs! In fact, complete graphs are the most highly regular graphs possible - they achieve maximum regularity.

Property 3: Diameter and Distance

The diameter of \(K_n\) (for \(n \geq 2\)) is 1.

Why? Because every vertex is directly connected to every other vertex, so the maximum shortest path length is 1.

Property 4: Chromatic Properties

The chromatic number \(\chi(K_n) = n\).

This means you need \(n\) different colors to properly color \(K_n\) because every vertex is adjacent to every other vertex - no two vertices can share the same color.

Property 5: Cliques

Every complete graph is a clique - a maximal set of mutually adjacent vertices. In fact, \(K_n\) is the unique graph that is both a clique and a complete graph on \(n\) vertices.

Visualizing Complete Graphs

Let’s explore complete graphs from small to large to build intuition.

Small Complete Graphs

K₁, K₂, K₃: The Foundations

\(K_1\): A single vertex, 0 edges. Trivial but important as a base case.
\(K_2\): Two vertices, 1 edge. The simplest non-trivial graph.
\(K_3\): Three vertices, 3 edges. Forms a triangle - the first “interesting” complete graph.

Edge count verification:
- \(K_1\): \(\frac{1(0)}{2} = 0\) ✓
- \(K_2\): \(\frac{2(1)}{2} = 1\) ✓
- \(K_3\): \(\frac{3(2)}{2} = 3\) ✓

K₄: The Tetrahedron

\(K_4\) has 4 vertices and \(\frac{4 \times 3}{2} = 6\) edges. This is also the graph of a tetrahedron (triangular pyramid), one of the Platonic solids. Notice how every vertex has degree 3.

Interesting fact: \(K_4\) is the largest complete graph that can be drawn in the plane without edge crossings (it is planar).

K₅: Non-Planar Territory

\(K_5\) has 5 vertices and \(\frac{5 \times 4}{2} = 10\) edges. Each vertex has degree 4.

Historical importance: \(K_5\) is one of the two forbidden minors that characterize planar graphs (along with \(K_{3,3}\)). This means any non-planar graph must contain \(K_5\) or \(K_{3,3}\) as a minor.

Complete Graphs as Regular Graphs

Since complete graphs are regular, all our formulas for regular graphs apply!

Degree-Edge Relationship

For a \(k\)-regular graph of order \(n\): \(|E| = \frac{nk}{2}\)

For complete graph \(K_n\), we have \(k = n - 1\):
\[|E| = \frac{n(n-1)}{2}\]

This confirms our edge formula from a different angle!

Handshaking Lemma Application

The sum of all degrees equals twice the number of edges:
\[\sum_{v \in V} \text{deg}(v) = 2|E|\]

For \(K_n\):
\[n \times (n-1) = 2 \times \frac{n(n-1)}{2} = n(n-1)\]

Perfect consistency! ✓

Edge Growth: How Fast Do Complete Graphs Grow?

As we add vertices to a complete graph, the number of edges grows quadratically.

Graph	Vertices (n)	Edges	Degree per Vertex
\(K_1\)	1	0	0
\(K_2\)	2	1	1
\(K_3\)	3	3	2
\(K_4\)	4	6	3
\(K_5\)	5	10	4
\(K_6\)	6	15	5
\(K_7\)	7	21	6
\(K_8\)	8	28	7
\(K_{10}\)	10	45	9
\(K_{20}\)	20	190	19
\(K_{100}\)	100	4,950	99

Notice how the edges grow much faster than the vertices! This is the essence of \(O(n^2)\) growth.

Complete Graphs vs. Other Graph Types

Complete vs. Cycle Graphs

Cycle graph \(C_n\): 2-regular, forms a ring
Complete graph \(K_n\): \((n-1)\)-regular, fully connected

\(C_5\) has 5 edges (each vertex degree 2)
\(K_5\) has 10 edges (each vertex degree 4)

\(K_n\) contains \(C_n\) as a subgraph (you can select edges from \(K_n\) to form a cycle).

Complete vs. Path Graphs

Path graph \(P_n\): Sparse, tree-like structure
Complete graph \(K_n\): Dense, maximally connected

\(P_5\) has 4 edges
\(K_5\) has 10 edges

Complete vs. Empty Graphs

The complement of \(K_n\) is the empty graph \(\overline{K_n}\) with \(n\) vertices and no edges.

Applications of Complete Graphs

Complete graphs appear in many real-world scenarios:

1. Tournament Scheduling

In a round-robin tournament where every team plays every other team once, the match schedule forms a complete graph where:
- Vertices = teams
- Edges = matches

2. Network Topologies

A fully connected network (where every node can directly communicate with every other node) is modeled by a complete graph.

3. Chemistry: Molecular Structures

Certain molecular structures where every atom bonds with every other atom can be represented as complete graphs.

4. Clique Detection

Finding the largest complete subgraph (clique) in a graph is a fundamental problem in:
- Social network analysis (finding tightly-knit groups)
- Bioinformatics (protein interaction networks)
- Data mining (pattern recognition)

5. Optimization Problems

Many optimization problems use complete graphs as starting points:
- Traveling Salesman Problem (TSP): Find shortest route visiting all cities
- Maximum matching problems
- Graph coloring problems

Practice Problems

Test your understanding with these problems!

Problem 1: Edge Counting

Question: How many edges does \(K_{12}\) have?

Click to reveal solution

Solution:

Using the edge formula: |E| = n(n-1)/2

For K₁₂:

|E| = 12 × 11 / 2 = 132 / 2 = 66

Answer: 66 edges

Problem 2: Regularity

Question: What is the degree of each vertex in \(K_{15}\)? Is this graph regular?

Click to reveal solution

Solution:

In a complete graph K_n, each vertex connects to all other vertices.

Number of other vertices = n - 1 = 15 - 1 = 14

Therefore, each vertex has degree 14.

Since all vertices have the same degree, K₁₅ is 14-regular.

Answer: Degree = 14, Yes it is 14-regular

Problem 3: Finding n from Edge Count

Question: A complete graph has 21 edges. How many vertices does it have?

Click to reveal solution

Solution:

We know: |E| = n(n-1)/2

Given: |E| = 21

So: n(n-1)/2 = 21

n(n-1) = 42

We need to find n such that n × (n-1) = 42

Testing values:

6 × 5 = 30 (too small)
7 × 6 = 42 ✓

Answer: n = 7 vertices (the graph is K₇)

Problem 4: Subgraph Counting

Question: How many distinct triangles (\(K_3\) subgraphs) are contained in \(K_6\)?

Click to reveal solution

Solution:

A triangle requires choosing 3 vertices from the 6 available vertices.

Since K₆ is complete, any 3 vertices form a triangle.

Number of ways to choose 3 from 6:

C(6,3) = 6!/(3! × 3!) = (6 × 5 × 4)/(3 × 2 × 1) = 120/6 = 20

Answer: 20 triangles

Problem 5: Degree Sum

Question: What is the sum of all vertex degrees in \(K_8\)?

Click to reveal solution

Solution:

K₈ has 8 vertices, each with degree 8 - 1 = 7

Sum of all degrees = 8 × 7 = 56

We can verify this using the Handshaking Lemma:

Number of edges in K₈: |E| = 8 × 7 / 2 = 28

Sum of degrees = 2|E| = 2 × 28 = 56 ✓

Answer: 56

Problem 6: Chromatic Number

Question: Why does \(K_n\) require exactly \(n\) colors?

Click to reveal solution

Solution:

In graph coloring, adjacent vertices must have different colors.

In K_n, every vertex is adjacent to every other vertex.

This means:

No two vertices can share the same color
We need a unique color for each vertex
Therefore, we need exactly n colors

You cannot do it with fewer colors (any two vertices are adjacent), and you don't need more (one color per vertex suffices).

Answer: χ(K_n) = n because every vertex is adjacent to every other vertex

Problem 7: Maximum Density

Question: Prove that \(K_n\) has the maximum number of edges for any simple graph with \(n\) vertices.

Click to reveal solution

Proof:

In a simple graph (no multi-edges, no self-loops):

Each pair of vertices can have at most 1 edge
Number of distinct pairs from n vertices = C(n,2) = n(n-1)/2
K_n has exactly this many edges
Therefore, K_n achieves the maximum

Any graph with more edges would require multiple edges between vertices (making it a multigraph, not a simple graph).

Conclusion: K_n is maximally dense ∎

Problem 8: Complement Graph

Question: What is the complement of \(K_5\)? How many edges does it have?

Click to reveal solution

Solution:

The complement graph G̅ contains all edges NOT in G.

Since K₅ contains ALL possible edges, its complement contains NO edges.

The complement of K₅ is the empty graph on 5 vertices (often denoted N₅ or K̅₅).

Answer: The empty graph with 5 vertices and 0 edges

Generating Complete Graphs in Python

For practical work with complete graphs, Python’s networkx library is excellent:

import networkx as nx
import matplotlib.pyplot as plt

# Create a complete graph with n vertices
n = 6
G = nx.complete_graph(n)

# Display basic properties
print(f"Order (vertices): {G.number_of_nodes()}")
print(f"Size (edges): {G.number_of_edges()}")
print(f"Expected edges: {n*(n-1)//2}")

# Check if it's regular
degrees = [deg for node, deg in G.degree()]
print(f"All degrees: {degrees}")
print(f"Is {n-1}-regular: {all(d == n-1 for d in degrees)}")

# Visualize
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, 
        node_color='lightblue', 
        node_size=500,
        edge_color='gray',
        font_size=12,
        font_weight='bold')
plt.title(f"Complete Graph K{n}")
plt.axis('off')
plt.show()

Output:

Order (vertices): 6
Size (edges): 15
Expected edges: 15
All degrees: [5, 5, 5, 5, 5, 5]
Is 5-regular: True

Key Takeaways

Let’s summarize what makes complete graphs special:

Definition: Every vertex connects to every other vertex - maximum connectivity
Notation: \(K_n\) for a complete graph with \(n\) vertices
Edge Formula: \(|E| = \frac{n(n-1)}{2}\) - quadratic growth
Regularity: Every \(K_n\) is \((n-1)\)-regular
Maximum Density: \(K_n\) has the most edges possible for \(n\) vertices
Diameter: Always 1 (for \(n \geq 2\)) - everything is one hop away
Chromatic Number: Requires \(n\) colors
Planarity: Only \(K_1\), \(K_2\), \(K_3\), and \(K_4\) are planar

Complete graphs represent the extreme case of graph density and serve as important reference structures throughout graph theory. Whether you’re studying network design, scheduling problems, or theoretical graph properties, understanding complete graphs provides a solid foundation.

Explore Further

Ready to experiment? Use the GraphArena Playground to:
- Create your own complete graphs
- Verify edge counts and degree sequences
- Compare complete graphs to other regular graphs
- Visualize larger complete graphs like \(K_8\) or \(K_{10}\)
- Extract subgraphs and find cliques

Understanding complete graphs deeply will help you recognize when problems can be solved using maximum-density structures and when sparser graphs are more appropriate. They’re the densest regular graphs possible and serve as upper bounds for many graph properties!