Empty Graph — Definition, Formula & Examples

An empty graph is a graph that contains one or more vertices but has no edges connecting any of them. Every vertex in an empty graph is isolated.

An empty graph (also called an edgeless graph or null graph) on $n$ vertices, denoted $\overline{K_n}$ or $E_n$ , is the graph $G = (V, E)$ where $|V| = n$ and $E = \emptyset$ . It is the complement of the complete graph $K_n$ .

Key Formula

\overline{K_n} = (V, \emptyset) \quad \text{where } |V| = n

Where:

$n$ = The number of vertices in the graph
$V$ = The vertex set
$\emptyset$ = The empty set, indicating no edges

How It Works

An empty graph on

n

vertices consists of

n

isolated points with no connections between them. Because it has no edges, its edge count is 0, every vertex has degree 0, and its adjacency matrix is the

n \times n

zero matrix. The empty graph serves as a boundary case in many graph-theoretic proofs and algorithms, representing the extreme opposite of the complete graph.

Example

Problem: Determine the number of edges, the degree of each vertex, and the chromatic number of the empty graph on 5 vertices.

Edge count: An empty graph has no edges by definition.

|E| = 0

Vertex degrees: Since no edges exist, no vertex is connected to any other. Every vertex has degree 0.

\deg(v_i) = 0 \quad \text{for all } i = 1, 2, 3, 4, 5

Chromatic number: Because no two vertices are adjacent, you can color every vertex the same color without any conflict.

\chi(\overline{K_5}) = 1

Answer: The empty graph

\overline{K_5}

has 0 edges, every vertex has degree 0, and its chromatic number is 1.

Why It Matters

Empty graphs appear frequently as base cases in inductive proofs and as starting states in greedy algorithms that build up edge sets. In Ramsey theory and extremal graph theory, they represent one of the two extremes (alongside complete graphs) that bound the structures being studied.

Common Mistakes

Mistake: Confusing an empty graph with the "null graph" that has no vertices at all.

Correction: Terminology varies by author. Many texts use "null graph" to mean a graph with zero vertices and zero edges, while "empty graph" specifically means vertices exist but no edges do. Always check your textbook's convention.