# Equivalence of Definitions of Reachable

## Contents

## Theorem

The following definitions of the concept of **Reachable** are equivalent:

### Definition 1

Let $G = \left({V, A}\right)$ be a directed graph.

Let $u, v \in V$.

Then $v$ is **reachable** from $u$ if and only if there exists a directed walk from $u$ to $v$.

### Definition 2

Let $G = \left({V, A}\right)$ be a directed graph.

Let $\mathcal R$ be the reachability relation of $G$.

That is, $\mathcal R$ is the transitive closure of $A$.

Let $u, v \in V$.

Then $v$ is **reachable** from $u$ if and only if $u \mathrel {\mathcal R} v$.

## Proof

Let $G = \left({V, A}\right)$ be a directed graph.

Let $u, v \in V$.

Let $\mathcal R$ be the reachability relation for $G$, defined as the transitive closure of $A$.

### Definition 1 implies Definition 2

Suppose that $v$ is reachable from $u$ by definition 1.

Then there exists a directed walk $\left({u = x_0, \dots, x_n = v}\right)$ from $u$ to $v$.

Then by the definition of directed walk:

- $x_0 \mathrel {\mathcal R} x_1 \mathrel {\mathcal R} \cdots \mathrel {\mathcal R} x_n$

Then by the definition of transitive closure:

- $u \mathrel {\mathcal R} v$

Thus $v$ is reachable from $u$ by definition 2.

$\Box$

### Definition 2 implies Definition 1

Suppose that $v$ is reachable from $u$ by definition 2.

That is:

- $u \mathrel {\mathcal R} v$

Thus by the definition of transitive closure:

- $\exists x_0, \ldots, x_n \in V: x_0 \mathrel {\mathcal R} x_1 \mathrel {\mathcal R} \cdots \mathrel {\mathcal R} x_n$

Then $\left({x_0 \mathrel {\mathcal R} x_1 \mathrel {\mathcal R} \cdots \mathrel {\mathcal R} x_n}\right)$ is a directed walk from $u$ to $v$.

Therefore, $v$ is reachable from $u$ by definition 1.

$\blacksquare$