# Definition:Incident (Graph Theory)

Jump to navigation
Jump to search

## 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:

- $u$ and $v$ are each
**incident with $e$** - $e$ is
**incident with $u$**and**incident with $v$**.

## Digraph

Let $G = \struct {V, E}$ be a digraph.

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

Let $e = \tuple {u, v}$ 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 $e$ of $G$ if $e$ is one of those which surrounds the face.

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

In the above graph, for example, the face $ABHC$ is incident to: