What is the difference between an edge in a directed graph and an undirected graph?

In an undirected graph, the edge {A, B} connects A and B with no direction — you can travel either way. In a directed graph, the edge (A, B) goes specifically from A to B, like a one-way street. The edge (B, A) would be a separate, distinct edge going the opposite direction.

Edge (Graph Theory) — Definition, Formula & Examples

An edge (in graph theory) is a link that connects two vertices (nodes) in a graph. Each edge represents a relationship or connection between a pair of vertices.

Given a graph $G = (V, E)$ , an edge $e \in E$ is an element of the edge set, defined as an unordered pair $\{u, v\}$ of vertices in an undirected graph or an ordered pair $(u, v)$ in a directed graph. A graph may contain multiple edges between the same pair of vertices (a multigraph) or an edge from a vertex to itself (a loop).

Key Formula

|E| \leq \frac{n(n-1)}{2}

Where:

$|E|$ = Number of edges in a simple undirected graph (no loops or repeated edges)
$n$ = Number of vertices, i.e., $n = |V|$

How It Works

Edges are the fundamental building blocks of a graph alongside vertices. To describe a graph, you list its vertices and then specify which pairs are connected by edges. For example, a social network graph might have people as vertices and friendships as edges. The number of edges meeting at a vertex determines that vertex's degree. When you draw a graph, each edge appears as a line or curve between two dots. Counting edges and analyzing how they connect vertices is central to problems like finding shortest paths, detecting cycles, and determining whether a graph is connected.

Worked Example

Problem: A simple undirected graph G has vertices {A, B, C, D} and edges {A, B}, {A, C}, {B, C}, {C, D}. Find the total number of edges, the degree of each vertex, and verify the Handshaking Lemma.

List the edges: The edge set is E = { {A,B}, {A,C}, {B,C}, {C,D} }.

|E| = 4

Find each vertex's degree: Count how many edges touch each vertex. A appears in 2 edges, B in 2, C in 3, and D in 1.

\deg(A)=2,\; \deg(B)=2,\; \deg(C)=3,\; \deg(D)=1

Verify the Handshaking Lemma: The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges.

2 + 2 + 3 + 1 = 8 = 2 \times 4 = 2|E| \;\checkmark

Answer: The graph has 4 edges. The degrees are A: 2, B: 2, C: 3, D: 1, and their sum (8) equals 2|E|, confirming the Handshaking Lemma.

Another Example

Problem: What is the maximum number of edges in a simple undirected graph with 6 vertices?

Apply the formula: For a simple graph, the maximum number of edges occurs when every pair of distinct vertices is connected (a complete graph).

|E|_{\max} = \frac{n(n-1)}{2} = \frac{6 \times 5}{2}

Calculate: Simplify the expression.

|E|_{\max} = \frac{30}{2} = 15

Answer: A simple undirected graph with 6 vertices can have at most 15 edges.

Why It Matters

Edges are essential in discrete mathematics and computer science courses, where you study networks, trees, and algorithms like Dijkstra's shortest path. In the real world, edges model connections in social networks, road maps, circuit design, and internet routing. Understanding edges and their properties is a prerequisite for nearly every topic in graph theory, from Euler paths to network flow problems.

Common Mistakes

Mistake: Confusing the number of edges with the number of vertices when calculating a vertex's degree.

Correction: The degree of a vertex is the number of edges incident to that specific vertex, not the total number of edges in the graph. Count only the edges that touch the vertex in question.

Mistake: Assuming two edges between the same pair of vertices are allowed in a simple graph.

Correction: A simple graph permits at most one edge between any pair of vertices and no loops. Multiple edges between the same pair require a multigraph.