Labeled Graph — Definition, Formula & Examples

A labeled graph is a graph in which every vertex is assigned a distinct name or identifier, so that two graphs with the same structure but different vertex labels are considered different.

A labeled graph on $n$ vertices is a graph $G = (V, E)$ where $V = \{v_1, v_2, \dots, v_n\}$ is an ordered set of distinguishable vertices and $E \subseteq \binom{V}{2}$ is a set of edges. Two labeled graphs are equal if and only if they share the same vertex set and the same edge set.

Key Formula

\text{Number of labeled graphs on } n \text{ vertices} = 2^{\binom{n}{2}}

Where:

$n$ = The number of distinctly labeled vertices
$\binom{n}{2}$ = The number of possible edges between n vertices

How It Works

When you label the vertices of a graph, the identity of each vertex matters. For instance, an edge between vertex 1 and vertex 2 is different from an edge between vertex 1 and vertex 3, even if both graphs are single-edge graphs on three vertices. This distinction dramatically increases the number of possible graphs. On

n

labeled vertices, there are

\binom{n}{2}

possible edges, and each edge is either present or absent, giving

2^{\binom{n}{2}}

labeled graphs in total. The contrast with unlabeled graphs—where only structure matters—is central to combinatorial enumeration in graph theory.

Worked Example

Problem: How many distinct labeled graphs exist on 4 vertices?

Step 1: Compute the number of possible edges between 4 labeled vertices.

\binom{4}{2} = \frac{4!}{2!\,2!} = 6

Step 2: Each of the 6 possible edges is independently included or excluded, so raise 2 to that power.

2^6 = 64

Answer: There are 64 distinct labeled graphs on 4 vertices.

Why It Matters

Labeled graphs are the default setting in many areas of computer science, where vertices represent identifiable objects like network nodes, database records, or users. Counting labeled structures (e.g., labeled trees via Cayley's formula) is a core topic in combinatorics courses and appears in algorithm analysis whenever distinct identity of elements matters.

Common Mistakes

Mistake: Confusing labeled and unlabeled graph counts. Students sometimes cite

2^{\binom{n}{2}}

as the total number of graphs on

n

vertices without specifying that this counts labeled graphs.

Correction: The number of unlabeled graphs (up to isomorphism) is far smaller. For

n = 4

, there are 64 labeled graphs but only 11 unlabeled graphs. Always state whether you are counting labeled or unlabeled structures.