Definition:Incident

Definition

Undirected Graph

Let $G = \left({V, E}\right)$ be an undirected graph.

Let $u, v \in V$ be vertices of $G$.

Let $e = \left\{{u, v}\right\} \in E$ be an edge of $G$:

Then $e = \left\{{u, v}\right\}$ is incident to $u$ and $v$, or joins $u$ and $v$.

Similarly, $u$ and $v$ are incident to $e$.

Digraph

Let $G = \left({V, E}\right)$ be a digraph.

Let $u, v \in V$ be vertices of $G$.

Let $e = \left({u, v}\right)$ be an arc that is directed from $u$ to $v$:

Then the following definitions are used:

Incident From

• $e$ is incident from $u$;

• $v$ is incident from $e$.

Incident To

• $e$ is incident to $v$;

• $u$ is incident to $e$.

Planar Graph

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

Then a face of $G$ is incident to an edge if the edge is one of those which surrounds the face.

Similarly, a face of $G$ is incident to a vertex if the vertex is at the end of one of those incident edges.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 1.3$