Adjacency, Incidence, and Neighborhoods

A graph records which pairs of vertices are joined by edges. Three related terms describe this information from different viewpoints: adjacency describes a relation between vertices, incidence describes the relation between a vertex and an edge, and a neighborhood collects the vertices adjacent to a chosen vertex. These ideas let us translate between an edge list and an adjacency list without relying on a drawing.

Throughout, graphs are finite and simple: they have no loops and no multiple edges. Thus an edge has two distinct endpoints, and there is at most one edge with any given pair of endpoints. The vertex set and edge set are written $V(G)$ and $E(G)$, and an edge with endpoints $u$ and $v$ is written $uv$. Since the graph is undirected, $uv$ and $vu$ name the same edge.

Adjacency and Incidence

Definition: Distinct vertices $u,v\in V(G)$ are adjacent if $uv\in E(G)$. If $uv\notin E(G)$, they are nonadjacent. A vertex $u$ and an edge $e\in E(G)$ are incident if $u$ is one of the two endpoints of $e$. Equivalently, the endpoints of an edge are incident with that edge.

Adjacency is a relation between two vertices; incidence is a relation between a vertex and an edge. For example, if $e=uv$, then $u$ and $v$ are adjacent to each other, and each is incident with $e$. Because the graph is simple, neither endpoint is $e$ itself, and there is no edge from a vertex to itself.

Two distinct edges are sometimes called adjacent edges if they share an endpoint. This use of “adjacent” still refers to a shared connection, but the objects being compared are edges rather than vertices. When reading a problem, check whether it is discussing adjacent vertices or adjacent edges.

Neighborhoods

Definition: For a vertex $v\in V(G)$, its neighborhood is the set of all vertices adjacent to it: $$ N(v)=\{u\in V(G): uv\in E(G)\}. $$

Because the graph is simple, $v\notin N(v)$: there is no loop $vv$. The neighborhood is a set, so each neighboring vertex appears only once. If $v$ has no adjacent vertices, then $N(v)=\varnothing$, and $v$ is called isolated. The empty graph has no vertices, so there is no vertex for which to form a neighborhood.

Each neighbor $u\in N(v)$ corresponds to the edge $uv$, which is incident with $v$. In a simple graph this correspondence is one-to-one: no two different edges can join the same pair of vertices.

Proposition: For any vertex $v$ in a simple graph, the neighbors in $N(v)$ correspond exactly to the edges incident with $v$. In particular, each $u\in N(v)$ gives the unique incident edge $uv$.

Proof. Let $u\in N(v)$. By the definition of neighborhood, $uv\in E(G)$, so $uv$ is an edge incident with $v$. Conversely, let $e$ be an edge incident with $v$. Since the graph has no loops, its other endpoint is some vertex $u\ne v$. Then $e=uv$, so $uv\in E(G)$ and $u\in N(v)$. Finally, if two edges both joined $u$ and $v$, they would be multiple edges, which are excluded in a simple graph. Thus the edge $uv$ is unique. $\square$

Reading an Edge List

An edge list gives the vertex set and then names every edge. To find $N(v)$, inspect each listed edge: include its other endpoint exactly when the edge has $v$ as an endpoint. This procedure uses the edge list directly; it does not require inferring connections from the order in which edges are written.

Worked Example: Finding Neighborhoods and Incidences

Let $G=(V,E)$ have vertex set $V=\{a,b,c,d,e\}$ and edge set $E=\{ab,ac,cd\}$. Find the neighborhood of each vertex and list the edges incident with $c$.

For $a$, the edges $ab$ and $ac$ have $a$ as an endpoint. Their other endpoints are $b$ and $c$, so $N(a)=\{b,c\}$. For $b$, the only edge containing $b$ is $ab$, so $N(b)=\{a\}$. For $c$, the edges containing $c$ are $ac$ and $cd$, giving $N(c)=\{a,d\}$. For $d$, the only such edge is $cd$, so $N(d)=\{c\}$. No edge contains $e$, so $N(e)=\varnothing$.

The edges incident with $c$ are $ac$ and $cd$. Their other endpoints, $a$ and $d$, are precisely the elements of $N(c)$.

Check: The three listed edges have endpoint pairs $a,b$, $a,c$, and $c,d$. The neighborhoods above record each pair in both directions: for instance, $b\in N(a)$ and $a\in N(b)$, while no listed edge has $e$ as an endpoint.

Reading and Checking an Adjacency List

An adjacency list gives, for each vertex, the set of vertices adjacent to it. A complete adjacency list has one entry for every vertex, including isolated vertices, whose entries are empty. For an undirected simple graph, each edge $uv$ must appear in both lists: $v$ in the list for $u$, and $u$ in the list for $v$. No vertex should appear in its own list, and no neighbor should be repeated.

Theorem: Suppose a list $L(v)$ is specified for every vertex $v$ in a finite set $V$. These lists describe a simple undirected graph on $V$ exactly when (1) every $L(v)$ is a subset of $V\setminus\{v\}$, (2) no entry is repeated, and (3) $u\in L(v)$ if and only if $v\in L(u)$. In that case the edge set is uniquely determined by the lists.

Proof. First suppose the lists describe a simple undirected graph $G$. Every listed neighbor of $v$ is a vertex different from $v$, because the graph has no loops. A list is a set of neighbors, so it contains no repeated entry. If $u\in L(v)$, the edge $uv$ exists; as the graph is undirected, this same edge makes $v\in L(u)$. The reverse implication follows in the same way. Thus all three conditions hold.

Conversely, suppose the three conditions hold. Define an edge set by including $uv$ whenever $u\in L(v)$ or, equivalently by condition (3), $v\in L(u)$. Each such pair has distinct endpoints by condition (1), so there are no loops. Treating $uv$ as an unordered pair creates at most one edge for that pair, so there are no multiple edges. The resulting graph is simple, and the symmetry condition ensures that the neighbors of each $v$ are exactly the entries in $L(v)$. Finally, any graph represented by these lists must have exactly these pairs as edges, so the edge set is unique. $\square$

Worked Example: Reconstructing a Graph from Adjacency Lists

Consider the following lists on $V=\{a,b,c,d,e,f\}$:

Vertex	Listed neighbors
$a$	$b,d$
$b$	$a,c,d$
$c$	$b,e$
$d$	$a,b,e$
$e$	$c,d$
$f$	none

To build the edge set, take each unordered pair listed by a vertex, recording it only once. From $a$, we obtain $ab$ and $ad$. From $b$, the pairs are $ab,bc,bd$, so the new ones are $bc$ and $bd$. From $c$, the pairs are $bc,ce$, adding $ce$. From $d$, the pairs are $ad,bd,de$, adding $de$. The list for $e$ gives $ce,de$, already recorded, and $f$ adds no edge. Thus $E=\{ab,ad,bc,bd,ce,de\}$.

Check the entries in both directions: $b$ appears in $a$'s list and $a$ in $b$'s; $d$ appears in $a$'s list and $a$ in $d$'s; the same check holds for $bc$, $bd$, $ce$, and $de$. No list contains its own vertex, and $f$'s empty list is consistent with there being no edge incident with $f$.

Check: Reading the reconstructed edge set gives $N(a)=\{b,d\}$, $N(b)=\{a,c,d\}$, $N(c)=\{b,e\}$, $N(d)=\{a,b,e\}$, $N(e)=\{c,d\}$, and $N(f)=\varnothing$. These match the six given lists exactly.

Direct Adjacency Is Not the Same as Being Nearby

A vertex belongs to $N(v)$ only when there is an edge directly joining it to $v$. Sharing a neighbor with $v$, or appearing elsewhere in the graph, does not by itself make a vertex adjacent to $v$. This distinction matters when converting lists: add only the endpoints of an edge, not every vertex that can be connected by following several edges.

Worked Example: A Shared Neighbor Does Not Give Adjacency

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,14,24,34\}$. Determine $N(1)$, $N(3)$, and whether $1$ and $3$ are adjacent.

The edges containing $1$ are $12$ and $14$, so $N(1)=\{2,4\}$. The only edge containing $3$ is $34$, so $N(3)=\{4\}$. The vertices $1$ and $3$ are not adjacent because the pair $13$ is not in $E$. Although they share the neighbor $4$, that does not add $3$ to $N(1)$ or $1$ to $N(3)$.

Check: The edge list contains $14$ and $34$, so each vertex is adjacent to $4$. It does not contain $13$, so there is no edge incident with both $1$ and $3$, and they are nonadjacent.

Common Pitfalls

Reversing an edge does not create a new edge. In an undirected graph, $ab$ and $ba$ name the same edge, not two different edges. For example, if $E=\{ab,bc\}$, the edge $ab$ contributes $b$ to $N(a)$ and $a$ to $N(b)$; it should not be counted as two edges.

Do not omit isolated vertices. If a graph has vertex set $\{p,q,r\}$ and edge set $\{pq\}$, then $r$ is still a vertex of the graph and $N(r)=\varnothing$. An adjacency list should include an entry for $r$, even though that entry is empty.

Do not include the vertex itself. If $N(a)$ is reported as $\{a,b\}$ in a simple graph, that is wrong: $a$ cannot be adjacent to itself because loops are excluded. For the edge list $E=\{ab\}$, the correction is $N(a)=\{b\}$.

Check symmetry in an undirected adjacency list. If $c$ appears in $L(b)$ but $b$ does not appear in $L(c)$, the lists do not consistently describe an undirected graph. Fix the lists before reconstructing the edge set.

Check Your Understanding

Use the definitions and list checks to answer each question.

For $V=\{u,v,w,x\}$ and $E=\{uv,vw\}$, find $N(u)$, $N(v)$, $N(w)$, and $N(x)$. Which vertex is isolated?
If $e=rs$, name the vertices incident with $e$. What does it mean for a vertex $t$ to be incident with an edge $e$?
On $V=\{1,2,3\}$, are the lists $L(1)=\{2\}$, $L(2)=\{1,3\}$, $L(3)=\{2\}$ consistent with a simple undirected graph? Give its edge set.
On $V=\{a,b,c\}$, explain why $L(a)=\{b\}$, $L(b)=\varnothing$, $L(c)=\varnothing$ cannot describe an undirected graph.
If two vertices share a neighbor but their pair is absent from the edge set, are they adjacent? Explain using the definition.

Vertex	Listed neighbors
\(a\)	\(b,d\)
\(b\)	\(a,c,d\)
\(c\)	\(b,e\)
\(d\)	\(a,b,e\)
\(e\)	\(c,d\)
\(f\)	none

Adjacency, Incidence, and Neighborhoods

What You'll Learn