Graph Edge — Definition, Formula & Examples

A graph edge is a connection linking two vertices (nodes) in a graph. Each edge represents a relationship or link between a pair of vertices.

In a graph $G = (V, E)$ , an edge $e \in E$ is an element of a set of unordered pairs (in an undirected graph) or ordered pairs (in a directed graph) drawn from the vertex set $V$ . For an undirected graph, an edge connecting vertices $u$ and $v$ is written $e = \{u, v\}$ ; for a directed graph, $e = (u, v)$ denotes an edge from $u$ to $v$ .

How It Works

An edge always connects exactly two vertices (or a vertex to itself, in the case of a loop). In an undirected graph, the edge

\{u, v\}

is the same as

\{v, u\}

. In a directed graph (digraph), the edge

(u, v)

goes from

u

v

, so order matters. A weighted edge carries an additional numerical value representing cost, distance, or capacity. The degree of a vertex counts how many edges are incident to it.

Worked Example

Problem: Given the graph

G = (V, E)

with

V = \{A, B, C, D\}

and

E = \{\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}\}

, determine the number of edges and the degree of vertex

C

Count the edges: List each element of

E

. There are four unordered pairs.

|E| = 4

Find the degree of C: Vertex

C

appears in the edges

\{A,C\}

\{B,C\}

, and

\{C,D\}

. Each occurrence adds one to its degree.

\deg(C) = 3

Answer: The graph has 4 edges, and vertex

C

has degree 3.

Why It Matters

Edges model real connections — roads between cities, friendships in social networks, links between web pages. Algorithms like Dijkstra's shortest path and Kruskal's minimum spanning tree operate directly on edges and their weights, making this concept foundational for computer science and operations research.

Common Mistakes

Mistake: Treating an undirected edge

\{u, v\}

as two separate edges.

Correction: In an undirected graph,

\{u, v\}

and

\{v, u\}

refer to the same single edge. Only in a directed graph are

(u, v)

and

(v, u)

distinct.