Adjacent Vertices — Definition, Formula & Examples

Adjacent vertices are two vertices (nodes) in a graph that are directly connected by an edge. If you can travel from one vertex to the other along a single edge, those vertices are adjacent.

In a graph $G = (V, E)$ , two vertices $u$ and $v$ are adjacent if and only if there exists an edge $e \in E$ such that $e = \{u, v\}$ . Adjacency is a symmetric relation in undirected graphs: if $u$ is adjacent to $v$ , then $v$ is adjacent to $u$ .

How It Works

To determine whether two vertices are adjacent, check whether an edge directly connects them. You do not follow a path through other vertices — only a single edge counts. In an adjacency matrix, vertices

v_i

and

v_j

are adjacent when the entry in row

i

, column

j

equals 1. The set of all vertices adjacent to a given vertex

v

is called the neighborhood of

v

, often written

N(v)

. The number of vertices adjacent to

v

equals the degree of

v

Worked Example

Problem: A graph has vertices

\{A, B, C, D\}

and edges

\{A, B\}

\{B, C\}

\{B, D\}

, and

\{C, D\}

. Which vertices are adjacent to

B

? Are

A

and

D

adjacent?

Find edges containing B: Look at every edge that includes vertex

B

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

List adjacent vertices of B: The other endpoint of each edge gives a vertex adjacent to

B

N(B) = \{A, C, D\}

Check A and D: Look for an edge

\{A, D\}

in the edge set. No such edge exists, so

A

and

D

are not adjacent.

Answer:

B

is adjacent to

A

C

, and

D

(so

\deg(B) = 3

). Vertices

A

and

D

are not adjacent because no edge connects them directly.

Why It Matters

Adjacency is the most basic relationship in graph theory and drives algorithms you encounter in computer science courses, such as breadth-first search and Dijkstra's shortest-path algorithm. Social networks, road maps, and circuit diagrams all rely on knowing which nodes connect directly to which others.

Common Mistakes

Mistake: Calling two vertices adjacent when they are connected by a path but not by a single edge.

Correction: Adjacency requires a direct edge between the two vertices. Being reachable through intermediate vertices does not make two vertices adjacent.